---
title: "Difference array"
url: https://algopath.pro/patterns/difference-array
language: en
summary: "Record the change at each index instead of the value. A range update costs two writes, and one final pass rebuilds everything."
updated: 2026-08-24
---

# Difference array

Record the change at each index instead of the value. A range update costs two writes, and one final pass rebuilds everything.

## 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).

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

## When should you use Difference array?

- 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.

## What is the time and space complexity of Difference array?

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

## 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.

```javascript
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;
}
```

## 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.

## JavaScript

```javascript
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;
}
```

## Python

```python
def apply_range_updates(n, updates):
    diff = [0] * (n + 1)
    for l, r, val in updates:
        diff[l] += val
        diff[r + 1] -= val
    result = [0] * n
    running = 0
    for i in range(n):
        running += diff[i]
        result[i] = running
    return result
```

## PHP

```php
function applyRangeUpdates(int $n, array $updates): array {
    $diff = array_fill(0, $n + 1, 0);
    foreach ($updates as [$l, $r, $val]) {
        $diff[$l] += $val;
        $diff[$r + 1] -= $val;
    }
    $result = array_fill(0, $n, 0);
    $running = 0;
    for ($i = 0; $i < $n; $i++) {
        $running += $diff[$i];
        $result[$i] = $running;
    }
    return $result;
}
```