Difference Array | Engineering Interview Kit

Concept

If a Prefix Sum allows you to do instant $O(1)$ Reads on a range, a Difference Array allows you to do instant $O(1)$ Writes (updates) on a range.

Imagine you have an array of 100,000 zeros. You are given 10,000 commands that look like: “Add +5 to all numbers between index 200 and index 50,000.”
If you write a for loop to update every single index for every single command, it will take $O(N \times K)$ time (where $K$ is the number of commands), completely freezing your application.

A Difference Array solves this by only recording the boundaries of the change.

Mental Model

Original Array (All Zeros): [0, 0, 0, 0, 0, 0]
Difference Array (All Zeros): [0, 0, 0, 0, 0, 0]

Command 1: Add +3 to the range [1, 4].
Instead of updating indices 1, 2, 3, and 4, we only update the edges in the Difference Array:

Add +3 at the start index (1).
Subtract -3 at the index exactly after the end boundary (5).

Difference Array becomes: [0, +3, 0, 0, 0, -3]

Command 2: Add +2 to the range [2, 3].

Add +2 at index 2.
Subtract -2 at index 4.

Difference Array becomes: [0, 3, +2, 0, -2, -3]

The Magic (Reconstruction):
When you have finished applying all 10,000 commands in $O(1)$ time each, you reconstruct the final array by calculating the Prefix Sum of the Difference Array.

Index 0: 0
Index 1: 0 + 3 = 3
Index 2: 3 + 2 = 5
Index 3: 5 + 0 = 5
Index 4: 5 + (-2) = 3
Index 5: 3 + (-3) = 0

Final Reconstructed Array: [0, 3, 5, 5, 3, 0].
This matches the exact desired output, achieved in just $O(N + K)$ total time!

Implementation

// Applies a list of queries [startIndex, endIndex, value] to an array of size N
function getModifiedArray(length: number, updates: number[][]): number[] {
    const diff = new Array(length).fill(0);

    // 1. Apply the boundary updates in O(1) time
    for (let [start, end, val] of updates) {
        diff[start] += val;
        
        // Only subtract if the end boundary isn't the absolute end of the array
        if (end + 1 < length) {
            diff[end + 1] -= val;
        }
    }

    // 2. Reconstruct the final array using Prefix Sum
    const result = new Array(length);
    let currentSum = 0;
    
    for (let i = 0; i < length; i++) {
        currentSum += diff[i];
        result[i] = currentSum;
    }

    return result;
}

Interview Questions

Q: A problem asks you to track flight bookings. You are given n flights (numbered 1 to n), and a list of bookings [first_flight, last_flight, seats_reserved]. You need to return an array of the total number of seats reserved on every single flight. How do you solve this?
A: This is LeetCode 1109 (Corporate Flight Bookings). It is literally the textbook definition of the Difference Array pattern.
Because the problem asks us to apply a single value (seats_reserved) across a massive continuous range of flights (first_flight to last_flight), we can process every booking in $O(1)$ time using a Difference Array (adding the seats to first_flight and subtracting them from last_flight + 1). Then, we do a single $O(N)$ sweep at the end to calculate the prefix sum, revealing the exact number of seats booked on every individual flight.