What Is a Difference Array? O(1) Range Updates, Explained
- Difference array stores D[i] = A[i] − A[i−1]; a single prefix sum pass reconstructs the original array.
- A range update on [l, r] costs two writes: D[l] += v and D[r+1] -= v, regardless of range size.
- Total complexity for m updates on a length-n array: O(n + m), versus O(n × m) brute force.
- Allocate n + 1 slots so writing D[r+1] is safe when r is the last valid index.
- Difference array vs prefix sum: prefix sum answers static range queries in O(1); difference array batches range updates cheaply with one final reconstruction.
- The 2D difference array uses four corner updates to apply a value to any rectangle in O(1).
You have an array of a hundred thousand time slots. A scheduling system needs to mark a range of them as booked. Then another range. Then ten thousand more. The naive approach visits every slot in every range, one at a time. For ten thousand bookings over a hundred thousand slots, that's a billion operations. Your laptop fans spin up. The test runner times out. The judge returns TLE and you stare at the screen wondering what you did wrong.
The difference array cuts every one of those range updates to two operations. Total cost: O(n + m) instead of O(n times m). And the trick fits in three lines of code.
Range Updates Kill Your Runtime
Take the simplest version of the problem. You have an array A of length n, initialized to zero. You receive m operations, each saying "add value v to every element between index l and index r." At the end, you read the final array.
The brute force costs O(r minus l plus 1) per operation. With m operations, worst case is O(n times m). At n = 100,000 and m = 100,000, that's ten billion operations. Ten billion. Your laptop weeps. The judge sends you a TLE and does not elaborate. The brute force will pass on the three-element example in the problem description and nowhere else.
The difference array makes each range update O(1) by deferring the actual work to a single O(n) reconstruction pass at the end.
The tradeoff is that you can't query individual elements cheaply during updates. The technique is built for one specific shape: many updates followed by a single read.
What a Difference Array Stores
Start with array A. The difference array D is defined as:
D[0] = A[0]
D[i] = A[i] - A[i-1] for i >= 1
For A = [3, 5, 8, 2, 7, 4]:
D = [3, 2, 3, -6, 5, -3]
You can reconstruct A from D using prefix sums. A[i] is the sum of D[0] through D[i]. Check it: A[2] = 3 + 2 + 3 = 8. A[4] = 3 + 2 + 3 + (-6) + 5 = 7. Correct.
D is the discrete derivative of A. Take the prefix sum of D and you recover A. That relationship is the entire basis of the technique.
Two Operations, Any Range Size
To add value v to every element in A[l..r]:
D[l] += v
D[r + 1] -= v
Two lines. The range can be one element or one million. Same cost. You might read that twice because it sounds too good to be true.
Why it works: when you reconstruct A via prefix sums, the +v at D[l] propagates forward to every index from l onward. The -v at D[r+1] cancels the propagation at r+1 and beyond. Every element in [l, r] ends up with v added. Everything outside is unchanged.
Trace it. A = [3, 5, 8, 2, 7, 4], D = [3, 2, 3, -6, 5, -3]. Add 10 to A[1..3]:
D[1] += 10 → D = [3, 12, 3, -6, 5, -3]
D[4] -= 10 → D = [3, 12, 3, -6, -5, -3]
Reconstruct via prefix sums:
A[0] = 3
A[1] = 3 + 12 = 15 (was 5, now 5 + 10 = 15 ✓)
A[2] = 15 + 3 = 18 (was 8, now 8 + 10 = 18 ✓)
A[3] = 18 + (-6) = 12 (was 2, now 2 + 10 = 12 ✓)
A[4] = 12 + (-5) = 7 (was 7, unchanged ✓)
A[5] = 7 + (-3) = 4 (was 4, unchanged ✓)
The cancellation at index 4 is doing the real work. The +10 enters the prefix sum stream at index 1 and the -10 removes it at index 4.
The Code
def apply_range_updates(n: int, updates: list[tuple[int, int, int]]) -> list[int]: diff = [0] * (n + 1) # n+1 slots so D[r+1] is safe when r = n-1 for l, r, val in updates: diff[l] += val diff[r + 1] -= val result = [] running = 0 for i in range(n): running += diff[i] result.append(running) return result
function applyRangeUpdates( n: number, updates: [number, number, number][] ): number[] { const diff = new Array(n + 1).fill(0); for (const [l, r, val] of updates) { diff[l] += val; diff[r + 1] -= val; } const result: number[] = []; let running = 0; for (let i = 0; i < n; i++) { running += diff[i]; result.push(running); } return result; }
Allocate n + 1 slots for the difference array. When r is the last valid index (n - 1), you write to diff[n]. Without the extra slot, that is an out-of-bounds write. This is the single most common mistake when implementing the pattern from memory, and it will not show up in small test cases, which makes it especially fun to debug under interview pressure.
If the original array is not zero but some baseline array, initialize diff from that array: diff[0] = A[0], diff[i] = A[i] - A[i-1]. Then apply updates on top.
Why the Numbers Work Out
| Operation | Brute force | Difference array |
|---|---|---|
| One range update | O(r - l + 1) | O(1) |
| m updates total | O(n times m) | O(m) |
| Reconstruction | none needed | O(n) |
| Full problem (m updates + read) | O(n times m) | O(n + m) |
| Space | O(1) extra | O(n) extra |
At m = 10,000 and n = 100,000, brute force costs up to one billion operations. The difference array costs 110,000. That's not a rounding error. That's four orders of magnitude.
The reconstruction step is unavoidable. But you pay it once at the end, not per update. If you only need a single value from the final array (say, the maximum), you still do the full O(n) reconstruction pass, then scan for the max. Still O(n + m).
Where It Shows Up in Interviews
LeetCode 1109 (Corporate Flight Bookings) is the canonical problem. Each booking reserves seats on a range of flight numbers. Apply all bookings as range updates. Reconstruct. Return the array.
LeetCode 1094 (Car Pooling) is structurally the same. Passengers board at one stop and exit at another. Range-update their count, reconstruct, check whether any value exceeds capacity. The trip's dropoff is the r+1 boundary.
LeetCode 995 (Minimum Number of K Consecutive Bit Flips) uses a parity variant of the difference array. Instead of summing absolute values, you track whether the current index has been flipped an odd or even number of times. The difference array tells you that in O(1) per position rather than rescanning the last k positions.
LeetCode 370 (Range Addition) is the template problem directly. It's behind a premium lock on LeetCode but widely reproduced. Given a zero array and a list of (start, end, inc) operations, return the final array.
The recognizable signal across all of these: you add a constant to every element in a range, repeatedly, and need the final state. Once you see that shape, the difference array is almost certainly the intended approach. The brute force will pass on small inputs and time out at n = 10^5. The real skill in an interview is recognizing the pattern before you code, not after you've already written the O(n times m) solution and have four minutes left on the clock.
Difference Array vs Prefix Sum
These two are inverses of each other, which is exactly why people confuse them.
Prefix sums solve the complementary problem: given a static array, answer "what is the sum of elements from l to r?" in O(1) after an O(n) setup. The array doesn't change. Queries are fast.
The difference array handles the opposite: a dynamic array with many writes, and a single read at the end. Updates are fast. Reading requires O(n) reconstruction.
| Technique | Range update | Range query | Best for |
|---|---|---|---|
| Prefix sum | O(n) | O(1) | Static arrays, many range-sum queries |
| Difference array | O(1) | O(n) | Many range updates, one final read |
| Fenwick tree | O(log n) | O(log n) | Interleaved point updates and prefix queries |
| Segment tree | O(log n) | O(log n) | Interleaved range updates and range queries |
If updates and queries are interleaved, neither prefix sum nor difference array is sufficient. You need a more powerful structure. The difference array shines exactly when you can batch all writes before any reads.
The 2D Difference Array
The same idea extends to 2D grids. To add v to every cell in the rectangle from (r1, c1) to (r2, c2):
diff[r1][c1] += v diff[r1][c2 + 1] -= v diff[r2 + 1][c1] -= v diff[r2 + 1][c2 + 1] += v
Four corner updates, always. Reconstruction requires two passes: first compute row-wise prefix sums, then column-wise (or the reverse). The four-corner update follows inclusion-exclusion: you add at the top-left, subtract at both edges to stop propagation, then add back the corner that got double-subtracted.
Allocate the 2D difference array with dimensions (rows + 1) by (cols + 1) for the same reason as the 1D case.
Recognizing It Before You Code
Look for all three of these at once:
- An array initialized to zero (or a fixed baseline).
- Multiple operations each adding a constant to a contiguous range.
- A read of the final array (or a derived query like "what is the maximum?") after all operations.
If all three are present, the difference array is almost certainly the intended approach. The brute force will pass on small inputs and time out at n = 10^5.
When explaining it in an interview: "I'll build a difference array. For each range update, I mark the start and the position after the end. A single prefix sum pass at the end reconstructs the final values. Each update is O(1). Reconstruction is O(n). Total: O(n + m)." That's everything the interviewer needs to hear.
The explanation part matters as much as the implementation. If you want rubric-based feedback on how clearly you walk through algorithmic reasoning under pressure, SpaceComplexity runs voice-based mock interviews that score exactly this. You explain the technique out loud, the AI interviewer pokes at your reasoning, and the feedback tells you where you were unclear before a real interviewer does.
Key Takeaways
- A difference array stores D[i] = A[i] - A[i-1], not A[i] itself.
- Range update [l, r] by v costs two operations: D[l] += v and D[r+1] -= v.
- Reconstruct the final array with one O(n) prefix sum pass.
- Total cost for m updates on a length-n array: O(n + m).
- Allocate the difference array with n + 1 slots to avoid an out-of-bounds write at D[r+1] when r = n - 1.