cf.completefrontend
ARRAYS & HASHING · CORE

Difference array

Apply many "add this amount to a range" updates in constant time each, then rebuild the final values in one pass.

Time O(n + u)Space O(n)7 practice problemsStep-through picture

The idea

Sometimes you get many updates of the form "add amount to every item from start to end" and only need the final values at the end. Applying each update item by item costs as much as the range is long.

A difference array records only where each change starts and stops. Add amount at start, and subtract it again just after end, at end + 1. Each update is two steps, however long its range.

At the end, a running total over the difference array rebuilds the real values: walking left to right, the +amount switches the change on and the -amount switches it off again. This is the reverse of a prefix sum.

An everyday example

Turning lights on and off along a hallway

A long hallway has a row of lamps. Instead of walking to each lamp in a range to brighten it, you put a note at the start of the range saying "brighter by 2 from here" and a note just past the end saying "back down by 2 from here". After all the notes are placed, you walk the hallway once, keeping track of the brightness as you pass each note. The brightness you carry at each lamp is its final value.

How the example maps to the code
In the exampleIn the code
The notes along the hallwaydiff
"Brighter by 2 from here"diff[start] += amount
"Back down by 2 from here"diff[end + 1] -= amount
The brightness you carry while walkingrunning
Each lamp's final brightnessresult[i] = running

From the slow way to difference array

  1. The obvious way to apply "add amount from start to end" is a loop over that range. A range can cover all n positions, so u updates cost up to n × u steps. 100,000 updates on 100,000 positions is 10 billion additions.
  2. Look at a single update. Inside its range, every position changes by the same amount, so neighbors inside the range stay the same distance apart. Only at the edges does anything happen between neighbors: the value jumps up by amount at start and drops back just after end.
  3. So record the gaps between neighbors instead of the values. An update changes just two gaps, the one at start and the one at end + 1, however long the range is. That is two writes per update instead of a loop.
  4. Values come back from gaps with a running total, the same way a prefix sum adds numbers up. Two writes per update and one pass at the end: that loop is a difference array.

How it works

  1. Create diff with n + 1 zeros. The extra slot catches updates that end at the last index.
  2. For each update [start, end, amount], do diff[start] += amount.
  3. And diff[end + 1] -= amount, which cancels it after the range.
  4. Walk i from 0 to n - 1, keeping running += diff[i].
  5. running is now the final value at i, so set result[i] = running.
  6. Return result.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function applyRangeAdds(n, updates) {
  2. const diff = new Array(n + 1).fill(0);
  3. for (const [start, end, amount] of updates) {
  4. diff[start] += amount;
  5. diff[end + 1] -= amount;
  6. }
  7. const result = new Array(n);
  8. let running = 0;
  9. for (let i = 0; i < n; i++) {
  10. running += diff[i];
  11. result[i] = running;
  12. }
  13. return result;
  14. }

How fast it is

TimeO(n + u)
Extra memoryO(n)

Each of the u updates writes two numbers, and the final pass visits each of the n positions once.

  • Best caseO(n + u)

    No input is faster: each update is two writes, and the rebuild always visits all n positions, even with zero updates.

  • Average caseO(n + u)

    Updates of any length cost the same two writes, so the total is the same for short and long ranges.

  • Worst caseO(n + u)

    Every update covers the whole array. Looping over ranges would cost n × u, but here each is still two writes.

Common mistakes

  • Making diff only n long, so an update that ends at the last index writes past the end.
  • Subtracting at end instead of end + 1 when the end is included, which drops the last position from every range.
  • Mixing 1-based positions from the problem with 0-based array indexes. Convert once, at the start.
  • Reading diff as if it held final values. Only the running total does.

When to use it

Look for these clues in a problem:

  • Many updates each add a value to a whole range, and you only need the final values after all of them.
  • The problem talks about bookings, shifts, or intervals that each add to a count over a span.
  • You need how many intervals cover each position, or the peak overlap.
  • Positions are small whole numbers (if they're huge, compress them first).

Check yourself

Answer each one in your head first, then open it.

In the trace, why is result[3] equal to -1?

At index 3 the first update has switched off and the second has switched on, while the third is still on: 1 - 2 = -1.

What does diff look like after the single update [2, 3, 5] with n = 5?

[0, 0, 5, 0, -5, 0], and the rebuilt result is [0, 0, 5, 5, 0].

Does the order of the updates change the result?

No. Each update only adds numbers into diff, and the same additions in any order give the same totals.

When is a difference array a poor fit?

When you need values in the middle of the updates. diff holds gaps, not values, so every read would need a full rebuild.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 7 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

Think of diff[i] as result[i] - result[i - 1], with result[-1] taken as 0. An update on start..end raises every value in the range by amount. Then the gap at start grows by amount, the gap at end + 1 shrinks by amount, and every other gap stays the same, because both of its neighbors moved together or neither did. Those are exactly the two writes.

Rebuilding adds the gaps from the left, so after step i, running is diff[0] + ... + diff[i]. The gaps cancel in pairs and leave result[i]. Another way to see it: an update adds amount to running from start onward and takes it back from end + 1 onward, so it counts exactly for start <= i <= end.

Updates only add numbers into diff, and adding doesn't depend on order, so updates can come in any order. The extra slot diff[n] holds the switch-off for updates that end at the last position. It belongs to no real position and is never read.

Going deeper

3 more ideas

Why the running total gives the right value

At position i, running is the sum of diff[0..i]. An update [start, end, amount] adds amount to that sum if start <= i, and removes it again if end + 1 <= i. So it counts exactly when start <= i <= end, which is the range it was meant to cover.

Counting overlaps and the peak

To count how many intervals cover each position, use amount = 1 for every interval. The largest running total is the most intervals that overlap at once, such as the peak number of viewers or the most meetings at the same time. Watch whether an interval's end is included: for half-open times [start, end), subtract at end, not end + 1.

Cost

Each of the u updates takes O(1), and rebuilding takes O(n), so the total is O(n + u) instead of O(n * u). It needs O(n) space. If positions go up to a billion, collect only the positions where changes happen, sort them, and sweep (coordinate compression or a sweep line).

Work it by hand

Every step in a table, with why

Apply three range updates to 6 positions, one with a negative amount and one ending at the last position, then rebuild the values.

n = 6, updates = [[0, 2, 4], [3, 5, 1], [1, 4, -2]]

StepPhaseUpdate or iChangediff or runningWhy
1update[0, 2, 4]diff[0] += 4, diff[3] -= 4[4, 0, 0, -4, 0, 0, 0]The change switches on at index 0 and off at index 3, just after the range ends.
2update[3, 5, 1]diff[3] += 1, diff[6] -= 1[4, 0, 0, -3, 0, 0, -1]end + 1 is 6, the extra slot. That is why diff has n + 1 slots. Two updates have now touched diff[3].
3update[1, 4, -2]diff[1] += -2, diff[5] -= -2[4, -2, 0, -3, 0, 2, -1]A negative amount works the same way: subtracting -2 at diff[5] adds 2.
4rebuildi = 0running += 4running = 4result[0] = 4. Only the first update covers index 0.
5rebuildi = 1running += -2running = 2result[1] = 2: the third update switches on here.
6rebuildi = 2running += 0running = 2result[2] = 2. No update starts or stops here, so the value repeats.
7rebuildi = 3running += -3running = -1The first update switches off (-4) and the second switches on (+1) at the same index: 2 - 4 + 1 = -1.
8rebuildi = 4running += 0running = -1result[4] = -1: still the second and third updates, 1 - 2.
9rebuildi = 5running += 2running = 1The third update switched off, so only the second remains. diff[6] is never read.

The result is [4, 2, 2, -1, -1, 1], from 6 writes for the updates and 6 additions to rebuild. Looping over each range would have taken 3 + 3 + 4 = 10 additions here, and far more with long ranges.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Difference arrayO(n + u)O(n)Many range updates first, then you read the final values once.
Add to every position in each rangeO(n · u)O(1)Few updates with short ranges, or you need the values after every update.
Fenwick tree over differencesO(u log n)O(n)Updates and point questions are mixed together.
Sort events and sweepO(u log u)O(u)Positions are huge or sparse, but there aren't many updates.

Extra memory: O(n): diff has n + 1 slots and result has n. You can rebuild into diff itself to save the second array.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Difference array and the other approaches, on a scale where each line up is 10 times more steps.
  • Difference array O(n + u)
  • Add to every position in each range O(n · u)
  • Fenwick tree over differences, Sort events and sweep O(u log n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Difference array202,0002 million
Add to every position in each range1001 million1 trillion
Fenwick tree over differences339,96620 million
Sort events and sweep339,96620 million

Inputs that need care

5 tricky inputs
No updates: n = 4, updates = []
diff stays all zeros and the result is [0, 0, 0, 0].
An update ending at the last position: [3, 5, 1] with n = 6
It writes diff[6], the extra slot. Without that slot, the write would land past the end of the array.
A single position: [2, 2, 5]
+5 at diff[2] and -5 at diff[3], so only position 2 changes.
start > end: [4, 2, 5] with n = 6
It writes -5 at diff[3] and +5 at diff[4], so position 3 wrongly gets -5. Reject or swap such updates before applying them.
Questions asked between updates
diff doesn't hold values until the rebuild, so each question would need a full pass. Use a Fenwick tree when updates and questions mix.

Variations and follow-ups

Twists interviewers add

Adding to rectangles in a grid

For a 2D range update, write +amount at the top-left corner, -amount just right of the top-right and just below the bottom-left, and +amount diagonally past the bottom-right. A 2D prefix sum at the end rebuilds every cell.

Updates and questions mixed: a Fenwick tree

Store diff in a Fenwick tree. A range update is still two point changes, and the value at one position is a prefix sum of diff, so both take O(log n).

Huge positions: sort the events

When positions are timestamps in the billions, an array of that size is impossible. Turn each update into two events, (start, +amount) and (end + 1, -amount), sort them, and keep the running total while sweeping through them in order.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "add x to every element from l to r", "bookings per day", "how many intervals cover each point", or "maximum overlap".
  • Explain it as switches: "each update switches a change on at start and off at end + 1, and a running total reads the switches."
  • Test by hand: an update ending at the last index, a single-position update, and a negative amount.
  • The usual follow-up is "what if questions come between updates?". Answer: a Fenwick tree over diff, or a segment tree with lazy updates, both O(log n) per operation.

Where frontend code uses it

The same idea in real UI code
  • A booking calendar can count how many reservations cover each day by adding +1 at each check-in day and -1 at each check-out day.
  • Finding the busiest minute of a live stream from viewers' join and leave times.
  • Text editors apply many range-based marks (highlights, diagnostics) and then need per-character counts; recording start and end changes is cheaper than touching every character.

Related algorithms