Difference array

Overview

A difference array lets you add a value to an entire range in O(1). Instead of updating every element in [l, r], you record the change at the start (diff[l] += v) and cancel it after the end (diff[r + 1] -= v). A single prefix sum over the difference array at the end reconstructs the final values.

It is the inverse of prefix sums: prefix sums make range queries fast, difference arrays make range updates fast. Use it whenever many range updates happen before you read the results.

When to use it

• Many range increments, followed by reading all values once.
• Counting how many intervals cover each point (bookings, trips, meetings).
• Line sweep: +1 when something starts, -1 when it ends.
• 2D versions: add a value to many sub-rectangles of a grid.

Problem patterns it solves

Where it is used in real software

Key terms

diff[i]

arr[i] - arr[i - 1]: how much the value changes at index i.

Range update

diff[l] += v and diff[r + 1] -= v.

Reconstruction

A prefix sum over diff gives the final array.

Line sweep

Process start and end events in coordinate order, maintaining a running count.

How it works, step by step

1. 1
   Allocate n + 1 slots

   The extra slot absorbs diff[r + 1] when r is the last index.

2. 2
   Apply each update in O(1)

   For [l, r, v]: diff[l] += v; diff[r + 1] -= v.

3. 3
   Prefix sum once

   running += diff[i]; result[i] = running.

4. 4
   Add the original array if needed

   If the array was not all zeros, add result[i] to the original values.

1109. Corporate Flight Bookings

bookings = [[1, 2, 10], [2, 3, 20], [2, 5, 25]], n = 5 flights (1-indexed)

Answer [10, 55, 45, 25, 25]. With b bookings and n flights, the cost is O(b + n) instead of O(b x n).

Implementation

1function applyRangeUpdates(n, updates) {2  const diff = new Array(n + 1).fill(0);3  for (const [l, r, v] of updates) {4    diff[l] += v;5    diff[r + 1] -= v;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}15 16// 1094. Car Pooling: never exceed capacity17function carPooling(trips, capacity) {18  const diff = new Array(1001).fill(0);19  for (const [passengers, from, to] of trips) {20    diff[from] += passengers;21    diff[to] -= passengers; // passengers leave at 'to', so no +122  }23  let onboard = 0;24  for (const change of diff) {25    onboard += change;26    if (onboard > capacity) return false;27  }28  return true;29}30 31// Sweep with sorted events when coordinates are large32function maxOverlap(intervals) {33  const events = [];34  for (const [start, end] of intervals) events.push([start, 1], [end, -1]);35  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]); // end before start at ties36  let current = 0, best = 0;37  for (const [, delta] of events) {38    current += delta;39    best = Math.max(best, current);40  }41  return best;42}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Array of size n instead of n + 1.

  Fix: diff[r + 1] must exist even when r = n - 1.

• Inclusive vs exclusive end.

  Fix: For [from, to) intervals like car pooling, subtract at to, not to + 1.

• Tie order in sweeps.

  Fix: Decide whether an end at time t frees capacity before a start at t, and sort accordingly.

Interview questions

Practice problems