Range Addition
Understanding the Problem
We start with an array of all zeros and need to apply a series of range update operations. Each operation says "add some value to every element from index start to index end." After all operations, we return the final array.
The direct approach is to loop through the range for each update and add the value. With many updates that each cover a large range, the total work grows as the product of the number of updates and the average range length, which becomes the bottleneck.
A faster approach avoids touching every element in the range. We record only where each update begins and ends, then sweep through the array once to compute the final values. This is the "difference array" technique, and it brings each update down to two constant-time operations.
Key Constraints:
1 <= length <= 10^5and0 <= updates.length <= 10^4→ With up to 100,000 elements and 10,000 updates, an approach that walks the full range of every update can reach 10^9 element updates in the worst case, which is too slow. This rules out brute force at the limits and motivates a faster method.0 <= startIdx_i <= endIdx_i < length→ Ranges are valid and within bounds, so the indices need no clamping.-1000 <= inc_i <= 1000→ Increments can be negative. The largest magnitude any element can reach is 10^4 updates times 1000, which is 10^7, well within a 32-bit signed integer.
Approach 1: Brute Force
Intuition
Do exactly what the problem describes. For each update operation, iterate through every index in the range [start, end] and add inc to each element. After processing all updates, the array holds the final values.
Algorithm
- Create an array
arrof sizelength, initialized to all zeros. - For each update
[start, end, inc], loop from indexstarttoendand addinctoarr[i]. - Return
arr.
Visualization and Code
Loading animation...
- Time Complexity: O(n x k), where n is the array length and k is the number of updates. Each update can touch up to n elements, and we have k updates.
- Space Complexity: O(n). We need the output array of size n. Beyond that, no extra space is used.
This is correct but slow when updates span large ranges. The next approach records each update in constant time and computes all final values in a single pass.
Approach 2: Difference Array (Prefix Sum)
Intuition
A range update [start, end, inc] has only two boundaries that matter. At index start, every element from that point onward gains inc. At index end + 1, that gain stops. A range update is therefore two events: an increase that begins at start and ends after end.
Record those two events instead of the whole range: add inc at start and subtract inc at end + 1. That captures the entire update in O(1) time. After recording all updates this way, sweep from left to right while keeping a running sum. At each position, the running sum equals the total increment that applies to that index.
A bus route makes the mechanism concrete. At stop 3, five people board. At stop 7, those five get off. Rather than counting passengers at every stop in between, record "+5 at stop 3" and "-5 at stop 7." Walking the stops with a running count gives the number of extra passengers on the bus at each stop, which is the prefix sum of those two events.
diff[i] stores the difference between consecutive final values, arr[i] - arr[i - 1] (with arr[-1] treated as 0). A range update changes that difference at exactly two places: it raises arr[start] relative to arr[start - 1] by inc, and it lowers arr[end + 1] relative to arr[end] by inc. Every difference inside the range is unchanged, because both endpoints of each interior step moved by the same inc.
The prefix sum inverts the difference. The running sum at index i adds up all the differences from 0 to i, which telescopes back to arr[i]. Any increment that started at or before i and has not yet been cancelled is still in the sum, so the final value at each index matches what the original range updates would have produced.
Algorithm
- Create a difference array
diffof sizelength, initialized to all zeros. - For each update
[start, end, inc]: - Add
inctodiff[start](the effect begins here). - If
end + 1 < length, subtractincfromdiff[end + 1](the effect ends afterend). - Compute the prefix sum of
diffin-place: for each index from 1 tolength - 1, adddiff[i - 1]todiff[i]. - Return
diff(it now contains the final array values).
Visualization and Code
Loading animation...
- Time Complexity: O(n + k), where n is the array length and k is the number of updates. Recording all updates takes O(k) since each update is two O(1) operations. Computing the prefix sum takes O(n).
- Space Complexity: O(n). We use a single array of size n. Since we need to return an array of size n anyway, this is effectively O(1) extra space beyond the output.