Difference array (range add)

42 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

A bus with 4 seats drives through stops 0, 1, 2, … Trip one: 2 people board at stop 1 and get off at stop 5. Trip two: 3 people board at stop 3 and get off at stop 7. Is the bus ever overfull?

By hand you would keep a tally for every stop and, for each trip, add its passengers to every stop it covers: trip one adds 2 to stops 1, 2, 3, 4; trip two adds 3 to stops 3, 4, 5, 6. Then read the tallies: 0, 2, 2, 5, 5, 3, 3, 0. Stop 3 has 5 people, over capacity.

The cost is the length of each trip. With q trips each covering up to n stops that is O(q · n). A thousand trips over a thousand stops is a million additions, and the same number appears in many problems: bookings on flights, flowers blooming between days, brightness of a row of lights.

Build the structure, one piece at a time

Instead of recording the load at each stop, record how the load changes from one stop to the next. Call that the difference array D. Boarding 2 people at stop 1 changes the load by +2 there; getting off at stop 5 changes it by −2 there. A whole trip is just two entries:

1. Trip (2 people, stops 1 → 5): D[1] += 2, D[5] −= 2.
2. Trip (3 people, stops 3 → 7): D[3] += 3, D[7] −= 3.

To read the actual loads, walk left to right keeping a running sum of D: that is a prefix sum, and the running sum at each stop is exactly the tally from the by-hand method. The two pieces of the structure are therefore: a change array that each range update touches in two places, and one prefix-sum sweep at the end that turns changes back into values.

Notice the convention: the subtraction goes at the first stop after the range ends. People who get off at stop 5 are not on the bus at stop 5, so the −2 sits at index 5. For a range that is inclusive on both ends, put the subtraction at r + 1.

Why it is correct

The invariant: the prefix sum of D up to index i equals the total added to position i by all updates so far. Look at one update "+k on [l, r)", recorded as D[l] += k and D[r] −= k. For i < l the prefix sum sees neither entry, contributing 0. For l ≤ i < r it sees +k only, contributing k. For i ≥ r it sees both, contributing k − k = 0. That is exactly "add k to positions l … r − 1 and nothing elsewhere". Prefix sums are additive, so several updates stack correctly: the sum of the contributions is the contribution of the sum.

Why it is fast

Each update costs 2 writes regardless of the range length, and the final sweep costs n additions. Total:

2q + n operations, O(n + q)

against O(q · n) for updating every position each time. For a thousand trips over a thousand stops that is about 3,000 operations instead of a million. The trick is to delay the work: updates are cheap because they only write down intentions, and the one sweep pays for all of them together.

How to recognise it in an interview

Cues: many operations of the form "add k to every element in a range", followed by a question about the final values or the maximum, with no reads in between. If reads and writes are interleaved you need a Fenwick tree or segment tree instead; if all the writes come first, the difference array is enough.

Say: "Each range add becomes two point edits in a difference array, and one prefix sum at the end recovers the values." Car Pooling is the example: the answer is whether the running sum ever exceeds the capacity. Corporate Flight Bookings is the same with seats on flights. Meeting Rooms II can be solved by +1 at each start and −1 at each end; the maximum running sum is the number of rooms needed.

02The idea in one line

Add at l, subtract at r+1; a prefix sum replays every range update.

Reach for it when: Many range increments, then read all values; car pooling, bookings.

Cost: O(n + q) time.

03The walk-through, step by step

The video works one example: Car Pooling trips [[2,1,5],[3,3,7]] capacity 4. These are its captions in order, so you can follow without the video or check a step you missed.

1. A range add becomes two point edits: +k at l, −k at r
2. Trip of 2 boards at stop 1: diff[1] += 2
3. …and leaves at stop 5: diff[5] −= 2
4. Trip of 3 boards at stop 3: diff[3] += 3
5. …and leaves at stop 7: diff[7] −= 3
6. Stop 0: load = 0 + (0) = 0
7. Stop 1: load = 0 + (2) = 2
8. Stop 2: load = 2 + (0) = 2
9. Stop 3: load = 2 + (3) = 5 > capacity!
10. Load peaks at 5 > 4 at stop 3: false
11. q updates + one prefix pass: O(n + q)

04Asked at Google

7 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Prefix Sums: Prefix sum + hashmap, Prefix and suffix products, 2D prefix sums.