Problem Statement

You are given an array arr of size n, where every element is initially 0.

There are m range increment operations.

Each operation is represented by three arrays:

For every operation:

Code
Increment(a[i], b[i], k[i])

Add k[i] to every element from index a[i] to b[i] (inclusive).

Your task is to return the maximum element in the array after performing all operations.

Example

Input

Code
n = 5

a = [0,1,2]
b = [1,4,3]
k = [100,100,100]

Initially:

Code
arr = [0,0,0,0,0]

Operation 1

Code
Increment(0,1,100)
Code
arr = [100,100,0,0,0]

Operation 2

Code
Increment(1,4,100)
Code
arr = [100,200,100,100,100]

Operation 3

Code
Increment(2,3,100)
Code
arr = [100,200,200,200,100]

Maximum element

Code
200

Naive Approach

A straightforward solution is:

For every operation:

Java
for(each operation){
    for(int j=a[i]; j<=b[i]; j++){
        arr[j] += k[i];
    }
}

Complexity

Code
Time = O(n × m)

If:

Code
n = 10^6
m = 10^6

then:

Code
10^12 operations

which is impossible within the time limit.

We need a better approach.

Efficient Approach – Difference Array

Instead of updating every element in a range, we only mark where an increment starts and where it ends.

This technique is called the Difference Array.

Instead of updating:

Code
[a....b]

we perform only two operations:

Code
diff[a] += k
diff[b+1] -= k

Later, while calculating the prefix sum, the increment automatically spreads over the entire range.

Why Does This Work?

Suppose:

Code
n = 6

Operation:

Code
+5 from index 1 to 4

Instead of:

Code
0 5 5 5 5 0

we store:

Index012345
Diff05000-5

Now compute the prefix sum.

Code
0
0+5 = 5
5+0 = 5
5+0 = 5
5+0 = 5
5-5 = 0

Result:

Code
0 5 5 5 5 0

Exactly the required array.

Algorithm

For every operation:

Code
(a,b,k)

Perform:

Java
diff[a] += k;

if(b+1<n)
    diff[b+1] -= k;

After processing all operations,

Compute the prefix sum.

Java
current += diff[i];

Track the maximum value during the traversal.

Dry Run

Input

Code
n = 5

a = [0,1,2]
b = [1,4,3]
k = [100,100,100]

Step 1

Initially:

Code
diff

0 0 0 0 0 0

(extra space is allocated to safely handle b + 1)

Operation 1

Code
0 → 1 (+100)
Code
diff[0]+=100
diff[2]-=100
Code
100 0 -100 0 0 0

Operation 2

Code
1 → 4 (+100)
Code
diff[1]+=100

No subtraction because:

Code
b+1 = 5

5 is outside the array.

Now:

Code
100 100 -100 0 0 0

Operation 3

Code
2 → 3 (+100)
Code
diff[2]+=100
diff[4]-=100

Final difference array:

Code
100 100 0 0 -100 0

Prefix Sum

Start with:

Code
current = 0

Index 0

Code
current = 100

Maximum = 100

Index 1

Code
current = 200

Maximum = 200

Index 2

Code
current = 200

Maximum = 200

Index 3

Code
current = 200

Maximum = 200

Index 4

Code
current = 100

Maximum = 200

Final Answer

Code
200

Java Solution

Java
class Solution {

    public int findMax(int n, int[] a, int[] b, int[] k) {

        // Difference array
        long[] diff = new long[n + 1];

        int m = a.length;

        // Apply all range updates
        for (int i = 0; i < m; i++) {

            // Increment starts here
            diff[a[i]] += k[i];

            // Increment ends after b[i]
            if (b[i] + 1 < n) {
                diff[b[i] + 1] -= k[i];
            }
        }

        long current = 0;
        long max = 0;

        // Build the final values using prefix sum
        for (int i = 0; i < n; i++) {

            current += diff[i];

            if (current > max) {
                max = current;
            }
        }

        return (int) max;
    }
}

Code Explanation

Creating the Difference Array

Java
long[] diff = new long[n + 1];

Instead of storing the actual array, we store only the changes.

n + 1 ensures that b + 1 can be handled safely.

Number of Operations

Java
int m = a.length;

The number of range updates is equal to the size of the input arrays.

Processing Every Operation

Java
for (int i = 0; i < m; i++)

Loop through all range increment operations.

Mark the Start of the Increment

Java
diff[a[i]] += k[i];

When we reach index a[i], all subsequent prefix sums should increase by k[i].

Mark the End of the Increment

Java
if (b[i] + 1 < n)
    diff[b[i] + 1] -= k[i];

After index b[i], the effect of the increment should stop.

Subtracting at b + 1 ensures that the running prefix sum decreases by k[i] from that point onward.

Prefix Sum

Java
current += diff[i];

The running sum reconstructs the final value at each index.

Update the Maximum

Java
if(current > max)
    max = current;

Keep track of the largest value while computing the prefix sum.

Return Answer

Java
return (int) max;

Return the maximum value after all range increment operations.

Why Use long?

Although the method returns an int, intermediate sums can become very large.

Example:

Maximum value:

Code
= 10^12

An int can store only up to:

Code
2,147,483,647

Using long prevents overflow during computation.

Complexity Analysis

Time Complexity

Overall:

Code
O(n + m)

Space Complexity

Difference array:

Code
O(n)

Key Takeaways

Summary

The Difference Array technique efficiently processes multiple range increment operations by recording only where each update begins and ends, rather than modifying every element in the affected range. A single prefix sum traversal then reconstructs the final array while tracking the maximum value. This approach reduces the time complexity from O(n × m) to O(n + m), making it practical for handling very large arrays and millions of update operations.