Difference Array: Efficient Range Updates

You are given an array of flight bookings where each booking adds a certain number of seats to every flight in a contiguous range. With thousands of bookings and tens of thousands of flights, how do you compute the final seat count for each flight without grinding through every range one by one? This is LeetCode 1109. Corporate Flight Bookings, and it is the perfect introduction to the difference array technique.

Why Brute Force Fails

The naive approach processes each booking by iterating through every index in its range and adding the value. If you have $k$ bookings and the array has $n$ elements, each booking could span the entire array, giving you $O(n \cdot k)$ time. When both $n$ and $k$ are on the order of $10^5$, that is $10^{10}$ operations, far too slow.

The waste is obvious: if a booking says "add 10 to flights 2 through 5000," you are performing 4999 additions that all encode the same information. There must be a way to record that information in constant time.

The Core Idea

Instead of modifying every element in the range $[l, r]$, create a difference array diff and make just two updates:

• diff[l] += val (the increment starts here)
• diff[r + 1] -= val (the increment stops after r)

After processing all operations, compute the prefix sum of diff. The result at each index is the final value of that element.

Why does this work? The +val at position l means "from here onward, everything is val higher." The -val at position r+1 cancels that effect, so positions beyond r are unaffected. When you take the prefix sum, these two markers propagate exactly the right adjustment to exactly the right range.

Walkthrough: Corporate Flight Bookings

To see how this works in LeetCode 1109, suppose we have $n = 5$ flights (1-indexed) and these bookings:

• Booking 1: flights 1 to 3, add 10
• Booking 2: flights 2 to 4, add 20
• Booking 3: flights 2 to 5, add 25

We create a difference array of size $n + 1$ (the extra slot avoids boundary checks):

diff = [0, 0, 0, 0, 0, 0] (indices 0 through 5, using 1-indexed flights)

Booking 1 (flights 1-3, val=10): diff[1] += 10, diff[4] -= 10 diff = [0, 10, 0, 0, -10, 0]

Booking 2 (flights 2-4, val=20): diff[2] += 20, diff[5] -= 20 diff = [0, 10, 20, 0, -10, -20]

Booking 3 (flights 2-5, val=25): diff[2] += 25, diff[6] is out of bounds, so we skip the subtraction (the effect lasts through the end). diff = [0, 10, 45, 0, -10, -20]

Now take the prefix sum of diff starting from index 1:

• Flight 1: 10
• Flight 2: 10 + 45 = 55
• Flight 3: 55 + 0 = 55
• Flight 4: 55 + (-10) = 45
• Flight 5: 45 + (-20) = 25

Final answer: [10, 55, 55, 45, 25]. Each booking was processed in $O(1)$ instead of $O(n)$.

Code: Corporate Flight Bookings

Here is the solution for LeetCode 1109:

def corpFlightBookings(bookings, n):
    diff = [0] * (n + 1)
    for first, last, seats in bookings:
        diff[first - 1] += seats
        if last < n:
            diff[last] -= seats
    # prefix sum
    for i in range(1, n):
        diff[i] += diff[i - 1]
    return diff[:n]

Two passes: one over the bookings ($O(k)$) and one prefix sum ($O(n)$). Total: $O(n + k)$.

The Relationship to Prefix Sums

Difference arrays and prefix sums are inverses of each other. If you take the prefix sum of an array and then compute the difference array of the result, you get the original array back, and vice versa.

• Prefix sum converts a difference array into an array of cumulative values.
• Difference array converts an array of values into an array of differences between consecutive elements.

Formally, if d[i] = a[i] - a[i-1] (with a[-1] = 0), then d is the difference array of a, and the prefix sum of d recovers a. This duality is why the difference array technique works: you record changes (differences), and a prefix sum reconstructs the values.

The Purest Form: Range Addition

LeetCode 370. Range Addition is the textbook version. You start with an array of zeros and apply a series of [start, end, val] operations. Return the final array.

def getModifiedArray(length, updates):
    diff = [0] * (length + 1)
    for start, end, val in updates:
        diff[start] += val
        diff[end + 1] -= val
    for i in range(1, length):
        diff[i] += diff[i - 1]
    return diff[:length]

This is the difference array pattern in its cleanest form: no indexing offsets, no extra constraints. If you internalize this template, every other variant is just a small twist.

Car Pooling: Difference Array on a Timeline

LeetCode 1094. Car Pooling asks: given trips where each trip is [numPassengers, from, to], and a vehicle with a fixed capacity, can you complete all trips without exceeding capacity?

Think of the timeline as an array indexed by location. Each trip is a range update: add passengers at from, remove them at to (they get off at to, so the subtraction is at to, not to + 1).

def carPooling(trips, capacity):
    diff = [0] * 1001  # locations range 0 to 1000
    for passengers, start, end in trips:
        diff[start] += passengers
        diff[end] -= passengers  # passengers exit at 'end'
    current = 0
    for d in diff:
        current += d
        if current > capacity:
            return False
    return True

Notice the subtlety: passengers leave at the to location, so we subtract at index to rather than to + 1. The problem defines the range as half-open: passengers are on board during $[from, to)$. Always read the problem carefully to determine whether the range endpoint is inclusive or exclusive.

2D Difference Array

The technique extends to two dimensions. To increment every cell in a submatrix from $(r_1, c_1)$ to $(r_2, c_2)$ by val, you make four updates to a 2D difference array:

diff[r1][c1]     += val
diff[r1][c2 + 1] -= val
diff[r2 + 1][c1] -= val
diff[r2 + 1][c2 + 1] += val

After all operations, compute the 2D prefix sum to recover the final matrix. The logic is the same inclusion-exclusion principle used in 2D prefix sums, just applied in reverse.

def apply_2d_difference(n, m, operations):
    diff = [[0] * (m + 1) for _ in range(n + 1)]
    for r1, c1, r2, c2, val in operations:
        diff[r1][c1] += val
        diff[r1][c2 + 1] -= val
        diff[r2 + 1][c1] -= val
        diff[r2 + 1][c2 + 1] += val
    # 2D prefix sum
    for i in range(n):
        for j in range(m):
            if i > 0:
                diff[i][j] += diff[i - 1][j]
            if j > 0:
                diff[i][j] += diff[i][j - 1]
            if i > 0 and j > 0:
                diff[i][j] -= diff[i - 1][j - 1]
    return [row[:m] for row in diff[:n]]

LeetCode 2536. Increment Submatrices by One is a direct application of this approach.

Complexity Analysis

• Time: $O(n + k)$ where $n$ is the array size and $k$ is the number of update operations. Each operation is $O(1)$, and the final prefix sum pass is $O(n)$.
• Space: $O(n)$ for the difference array.

For the 2D variant, time is $O(n \cdot m + k)$ and space is $O(n \cdot m)$.

Compared to the brute-force $O(n \cdot k)$, the difference array reduces the cost of each range update from $O(n)$ to $O(1)$, which is the entire point. It is one of the simplest and most satisfying optimizations in competitive programming.

Recognizing this pattern

You're probably looking at a difference array when:

• You see many range updates, such as "add v to all indices in [l, r]," "book seats from flight i to flight j," or "passengers board at from and exit at to," followed by a single readout of the final array.
• All updates are known up front (offline); you do not need to interleave queries between updates.
• You are asked for "peak occupancy," "maximum concurrent X," or "the time/index where the count is highest," which are read after applying all interval contributions.
• Coordinates are bounded enough that an array of size $n$ (or a compressed axis) fits in memory.
• The naive solution loops over each range and updates every index inside it, giving $O(n \cdot k)$.

Common templates:

• Pure range addition: diff[l] += v, diff[r + 1] -= v, prefix-sum to recover. Example: Range Addition.
• Timeline check / peak occupancy: apply +/- at entry/exit, prefix-sum, then test against a capacity. Example: Car Pooling.
• Counts after offline updates: many bookings, return the final per-slot count. Example: Corporate Flight Bookings.
• 2D difference array: four-corner update on a grid, then 2D prefix-sum. Example: Increment Submatrices by One.
• Implicit timeline via events: when coordinates are huge, store (time, delta) events, sort, and sweep, the same diff-array idea on a compressed axis. Example: My Calendar III.