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:

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

n = 5

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

Initially:

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

Operation 1

Increment(0,1,100)

arr = [100,100,0,0,0]

Operation 2

Increment(1,4,100)

arr = [100,200,100,100,100]

Operation 3

Increment(2,3,100)

arr = [100,200,200,200,100]

Maximum element

200

Naive Approach

A straightforward solution is:

For every operation:

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

Complexity

Time = O(n × m)

If:

n = 10^6
m = 10^6

then:

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:

[a....b]

we perform only two operations:

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:

n = 6

Operation:

+5 from index 1 to 4

Instead of:

0 5 5 5 5 0

we store:

Index012345
Diff05000-5

Now compute the prefix sum.

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

Result:

0 5 5 5 5 0

Exactly the required array.

Algorithm

For every operation:

(a,b,k)

Perform:

diff[a] += k;

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

After processing all operations,

Compute the prefix sum.

current += diff[i];

Track the maximum value during the traversal.

Dry Run

Input

n = 5

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

Step 1

Initially:

diff

0 0 0 0 0 0

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

Operation 1

0 → 1 (+100)

diff[0]+=100
diff[2]-=100

100 0 -100 0 0 0

Operation 2

1 → 4 (+100)

diff[1]+=100

No subtraction because:

b+1 = 5

5 is outside the array.

Now:

100 100 -100 0 0 0

Operation 3

2 → 3 (+100)

diff[2]+=100
diff[4]-=100

Final difference array:

100 100 0 0 -100 0

Prefix Sum

Start with:

current = 0

Index 0

current = 100

Maximum = 100

Index 1

current = 200

Maximum = 200

Index 2

current = 200

Maximum = 200

Index 3

current = 200

Maximum = 200

Index 4

current = 100

Maximum = 200

Final Answer

200

Java Solution

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

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

int m = a.length;

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

Processing Every Operation

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

Loop through all range increment operations.

Mark the Start of the Increment

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

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

current += diff[i];

The running sum reconstructs the final value at each index.

Update the Maximum

if(current > max)
    max = current;

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

Return Answer

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:

= 10^12

An int can store only up to:

2,147,483,647

Using long prevents overflow during computation.

Complexity Analysis

Time Complexity

Overall:

O(n + m)

Space Complexity

Difference array:

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.