Difference array

How does Difference array work?

Make an array of zeroes, one slot longer than the input. Each slot means the change at that index.

To add v across the range l to r, write two numbers. Add v at l and subtract v at r plus one.

That is the whole update. Nothing between l and r is touched.

Repeat for every range you are given. Each one costs two writes, whatever its width.

When the updates are done, take a running total across the array. Slot i then holds the real value.

The rebuild is a single pass. So m updates over n slots cost O(n + m).

1. diff = [0, 0, 0, 0, 0, 0]Five real slots plus one guard. Everything starts at zero.
2. diff = [0, 2, 0, 0, -2, 0]Add 2 across the range 1 to 3. Two writes, not three.
3. diff = [3, 2, -3, 0, -2, 0]Add 3 across the range 0 to 1. Again two writes.
4. running = [3, 5, 2, 2, 0]One pass of running totals rebuilds the values.
5. answer = [3, 5, 2, 2, 0]Two updates cost four writes. The width never mattered.

function applyRangeUpdates(n, updates) {
    const diff = new Array(n + 1).fill(0);
    for (const [l, r, val] of updates) {
        diff[l] += val;
        diff[r + 1] -= val;
    }
    const result = new Array(n);
    let running = 0;
    for (let i = 0; i < n; i++) {
        running += diff[i];
        result[i] = running;
    }
    return result;
}

A worked example of Difference array

Seats booked on each flight

You run n flights and receive a list of bookings. Each booking adds seats to every flight in a range.

Return the total number of seats booked on each flight.

A loop per booking would cost O(n) for a wide range.

Record each booking as two numbers instead. Take running totals once, after every booking is in.

function corpFlightBookings(bookings, n) {
    const diff = new Array(n + 1).fill(0);

    for (const [first, last, seats] of bookings) {
        diff[first - 1] += seats;
        diff[last] -= seats; // one slot past the end of the range
    }

    const answer = new Array(n);
    let running = 0;

    for (let i = 0; i < n; i++) {
        running += diff[i];
        answer[i] = running;
    }

    return answer;
}

When should you use Difference array?

These phrases in a problem statement point here:

• •many range updates first, then read the final array once
• •add a value to every element in a range, repeated many times
• •apply k range increments before answering any query
• •booking/interval counters over an array

What is Difference array confused with?

• Prefix sums: Prefix sums read many ranges from data that never changes. This is the mirror: many writes, one read.
• Sweep line (event counting): A sweep sorts events by coordinate, because the coordinates are huge or sparse. Here they index an array directly.
• Fenwick tree / segment tree: A Fenwick tree answers queries in between updates. A difference array only answers after the last one.
• Sliding window (fixed size): A window walks one span of fixed width. The ranges here differ in width and overlap freely.

Common mistakes with Difference array

• Sizing the array by n exactly

  A range ending at the last index writes to slot n. Allocate n plus one slots.

• Subtracting at r instead of r plus one

  The right edge is inclusive, so it must keep the change. Subtract one slot later.

• Reading a value before the rebuild

  The slots hold changes, not values, until the final pass. Ask questions only after it.

• Writing a single value directly

  One index is a range of width one. It still needs both writes.

Which interview problems use Difference array?

• Corporate flight bookings: Each booking is two writes over a range of flights.
• Range addition: The plain form of the pattern, with nothing else attached.
• Car pooling: Passengers get on and off, and the total must stay under the limit.
• Shifting letters II: Each shift covers a range of positions in the string.
• Maximum population year: A birth adds one and a death subtracts one.
• Meeting rooms II: A start adds a room, an end gives one back.
• Number of flowers in full bloom: Each flower covers a range of days.

What is the time and space complexity of Difference array?

O(n)

n up to 1e6 with m range updates gives O(n + m). Each update is two writes, and the rebuild is one pass.