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:
a[i] → Starting index
b[i] → Ending index
k[i] → Value to add
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:
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:
10^6 operations
Each adds 10^6
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
A naive range update modifies every element and takes O(n × m) time.
A Difference Array converts each range update into two constant-time operations.
A single Prefix Sum pass reconstructs the final array values.
This optimization reduces the complexity to O(n + m), making it suitable for arrays and operations as large as 10⁶.
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.
Join the conversation! Your thoughts help the community grow.