Difference Array — The Complete Guide

Goal: Add val to every element in range [l, r]

Instead of:  for (i = l; i <= r; i++) arr[i] += val;  // O(n) per update

Do this:     diff[l] += val;       // start the effect
             diff[r + 1] -= val;   // cancel the effect after r

After all updates: arr = prefixSum(diff)  // reconstruct in O(n)

Example: array of size 5, add 3 to range [1, 3]

diff = [0, 0, 0, 0, 0]
diff[1] += 3  →  [0, 3, 0, 0, 0]
diff[4] -= 3  →  [0, 3, 0, 0, -3]

Prefix sum:  [0, 3, 3, 3, 0]  ← exactly what we wanted!

The +3 at index 1 "carries forward" through the prefix sum.
The -3 at index 4 "cancels" it, so indices 4+ are unaffected.

function rangeAdd(n: number, updates: [number, number, number][]): number[] {
  // 1. Create difference array (size n+1 for safe r+1 access)
  const diff = new Array(n + 1).fill(0);

  // 2. Apply each update in O(1)
  for (const [l, r, val] of updates) {
    diff[l] += val;      // effect starts at l
    diff[r + 1] -= val;  // effect cancels after r
  }

  // 3. Prefix sum to reconstruct the actual array
  const result = new Array(n);
  result[0] = diff[0];
  for (let i = 1; i < n; i++) {
    result[i] = result[i - 1] + diff[i];
  }

  return result;
}
// Time: O(n + q) where q = number of updates
// Space: O(n)
// When to use: Range Update Array, Corporate Flight Bookings,
// any "add val to range [l, r]" batch problem

function rangeAddOnExisting(
  arr: number[],
  updates: [number, number, number][]
): number[] {
  const n = arr.length;

  // 1. Convert original array to difference array
  const diff = new Array(n + 1).fill(0);
  diff[0] = arr[0];
  for (let i = 1; i < n; i++) {
    diff[i] = arr[i] - arr[i - 1];
  }

  // 2. Apply updates in O(1) each
  for (const [l, r, val] of updates) {
    diff[l] += val;
    diff[r + 1] -= val;
  }

  // 3. Prefix sum to reconstruct
  const result = new Array(n);
  result[0] = diff[0];
  for (let i = 1; i < n; i++) {
    result[i] = result[i - 1] + diff[i];
  }

  return result;
}
// Key: diff[i] = arr[i] - arr[i-1] converts any array to its difference form.
// Prefix sum of the difference array gives back the original array.

function maxOverlap(intervals: [number, number][]): number {
  // Use a map when the range is sparse or values are large
  const events = new Map<number, number>();

  for (const [start, end] of intervals) {
    events.set(start, (events.get(start) ?? 0) + 1);  // interval starts
    events.set(end, (events.get(end) ?? 0) - 1);      // interval ends
  }

  // Sort events by time and sweep
  const sorted = [...events.entries()].sort((a, b) => a[0] - b[0]);

  let current = 0;
  let maxConcurrent = 0;

  for (const [, delta] of sorted) {
    current += delta;
    maxConcurrent = Math.max(maxConcurrent, current);
  }

  return maxConcurrent;
}
// When to use: maximum overlapping intervals, meeting rooms,
// car pooling, minimum platforms at a station
// Key: +1 at start, -1 at end, then sweep with running sum.

function rangeAdd2D(
  rows: number, cols: number,
  updates: [number, number, number, number, number][] // [r1, c1, r2, c2, val]
): number[][] {
  // 1. Create 2D difference array (extra row and column)
  const diff = Array.from({ length: rows + 1 }, () => new Array(cols + 1).fill(0));

  // 2. Apply each update in O(1)
  for (const [r1, c1, r2, c2, val] of updates) {
    diff[r1][c1] += val;
    diff[r1][c2 + 1] -= val;
    diff[r2 + 1][c1] -= val;
    diff[r2 + 1][c2 + 1] += val; // inclusion-exclusion correction
  }

  // 3. 2D prefix sum to reconstruct
  for (let r = 0; r < rows; r++) {
    for (let c = 1; c < cols; c++) {
      diff[r][c] += diff[r][c - 1]; // row prefix sum
    }
  }
  for (let c = 0; c < cols; c++) {
    for (let r = 1; r < rows; r++) {
      diff[r][c] += diff[r - 1][c]; // column prefix sum
    }
  }

  return diff.slice(0, rows).map(row => row.slice(0, cols));
}
// Time: O(rows × cols + q)
// When to use: stamp grid, 2D range updates, matrix block operations

function carPooling(trips: number[][], capacity: number): boolean {
  // Locations range from 0 to 1000
  const diff = new Array(1001).fill(0);

  for (const [passengers, from, to] of trips) {
    diff[from] += passengers;  // board at 'from'
    diff[to] -= passengers;    // exit at 'to' (not 'to + 1' — they exit BEFORE 'to')
  }

  // Sweep: check if capacity is ever exceeded
  let current = 0;
  for (let i = 0; i < diff.length; i++) {
    current += diff[i];
    if (current > capacity) return false;
  }

  return true;
}
// Time: O(n + 1001) where n = number of trips
// Space: O(1001) = O(1) since location range is bounded
// Key: passengers exit BEFORE the 'to' location, so diff[to] -= passengers
// (not diff[to + 1]). Read the problem carefully for inclusive/exclusive bounds.

function minMeetingRooms(intervals: number[][]): number {
  const events: [number, number][] = [];

  for (const [start, end] of intervals) {
    events.push([start, 1]);   // meeting starts → +1 room
    events.push([end, -1]);    // meeting ends → -1 room
  }

  // Sort by time. If same time, process ends (-1) before starts (+1)
  // so a room freed at time t can be reused by a meeting starting at t
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);

  let rooms = 0;
  let maxRooms = 0;

  for (const [, delta] of events) {
    rooms += delta;
    maxRooms = Math.max(maxRooms, rooms);
  }

  return maxRooms;
}
// Time: O(n log n) for sorting events
// Space: O(n) for events array
// Key: this is a difference array on a timeline.
// +1 at start, -1 at end, sweep for the peak.
// Sorting tie-break: ends before starts at the same time.

To add val to rectangle (r1,c1) → (r2,c2):

  diff[r1][c1]       += val   (top-left: start effect)
  diff[r1][c2+1]     -= val   (top-right+1: cancel rightward)
  diff[r2+1][c1]     -= val   (bottom+1-left: cancel downward)
  diff[r2+1][c2+1]   += val   (bottom+1-right+1: fix double subtraction)

This is inclusion-exclusion in 2D:
  ┌─────────┐
  │ +val    │-val
  │         │
  └─────────┘
  -val      +val  (correction)

After all updates, compute 2D prefix sum:
  1. Row-wise prefix sum (left to right)
  2. Column-wise prefix sum (top to bottom)

Result: each cell has the correct accumulated value.

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

Start: diff = [0, 0, 0, 0, 0, 0]  (size n+1 = 6)

Update 1: add 2 to range [1, 3]
  diff[1] += 2, diff[4] -= 2
  diff = [0, 2, 0, 0, -2, 0]

Update 2: add 3 to range [2, 4]
  diff[2] += 3, diff[5] -= 3
  diff = [0, 2, 3, 0, -2, -3]

Update 3: add -2 to range [0, 2]
  diff[0] += -2, diff[3] -= -2
  diff = [-2, 2, 3, 2, -2, -3]

Prefix sum to reconstruct:
  i=0: result[0] = -2
  i=1: result[1] = -2 + 2 = 0
  i=2: result[2] = 0 + 3 = 3
  i=3: result[3] = 3 + 2 = 5
  i=4: result[4] = 5 + (-2) = 3

Answer: [-2, 0, 3, 5, 3]

Verification (brute force):
  Start:    [0, 0, 0, 0, 0]
  +2 [1,3]: [0, 2, 2, 2, 0]
  +3 [2,4]: [0, 2, 5, 5, 3]
  -2 [0,2]: [-2, 0, 3, 5, 3]  ✓ Matches!

trips = [[2,1,5], [3,3,7]], capacity = 4

diff array (locations 0-7):
  diff = [0, 0, 0, 0, 0, 0, 0, 0]

Trip 1: 2 passengers, from=1, to=5
  diff[1] += 2, diff[5] -= 2
  diff = [0, 2, 0, 0, 0, -2, 0, 0]

Trip 2: 3 passengers, from=3, to=7
  diff[3] += 3, diff[7] -= 3
  diff = [0, 2, 0, 3, 0, -2, 0, -3]

Sweep (running sum):
  loc 0: current = 0  ≤ 4 ✓
  loc 1: current = 2  ≤ 4 ✓
  loc 2: current = 2  ≤ 4 ✓
  loc 3: current = 5  > 4 ✗ → EXCEEDS CAPACITY!

Answer: false

At location 3, both trips overlap: 2 + 3 = 5 passengers > capacity 4.

Key: diff[to] -= passengers (not diff[to+1]) because passengers
exit BEFORE reaching 'to'. Always check inclusive/exclusive bounds.

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

diff = [0, 0, 0, 0, 0, 0]  (size n+1 = 6, 0-indexed)

Booking 1: 10 seats on flights 1-2
  diff[0] += 10, diff[2] -= 10    (1-indexed → 0-indexed: l=0, r+1=2)
  diff = [10, 0, -10, 0, 0, 0]

Booking 2: 20 seats on flights 2-3
  diff[1] += 20, diff[3] -= 20
  diff = [10, 20, -10, -20, 0, 0]

Booking 3: 25 seats on flights 2-5
  diff[1] += 25, diff[5] -= 25
  diff = [10, 45, -10, -20, 0, -25]

Prefix sum:
  flight 1: 10
  flight 2: 10 + 45 = 55
  flight 3: 55 + (-10) = 45
  flight 4: 45 + (-20) = 25
  flight 5: 25 + 0 = 25

Answer: [10, 55, 45, 25, 25]

Verification:
  Flight 1: booking 1 = 10                    → 10  ✓
  Flight 2: booking 1 + 2 + 3 = 10+20+25      → 55  ✓
  Flight 3: booking 2 + 3 = 20+25             → 45  ✓
  Flight 4: booking 3 = 25                    → 25  ✓
  Flight 5: booking 3 = 25                    → 25  ✓

Does the problem involve range updates (add val to [l, r])?
├── NO  → Not a difference array problem
│         → Range queries? Use Prefix Sum
│         → Point updates + range queries? Use BIT or Segment Tree
└── YES → Do you need the result after EACH update?
          ├── YES → Use Segment Tree with lazy propagation (O(log n) per op)
          └── NO  → You only need the final state after ALL updates
                    ├── Is the range small and dense (fits in an array)?
                    │   ├── YES → Basic Difference Array (Template 1 or 2)
                    │   └── NO  → Sweep Line with Map (Template 3)
                    └── Is it a 2D grid?
                        ├── YES → 2D Difference Array (Template 4)
                        └── NO  → 1D Difference Array