Corporate Flight Bookings: Difference Array for Range Updates

You have n flights labeled from 1 to n. You are given an array bookings where bookings[i] = [first, last, seats] means that seats seats are reserved on every flight from first through last (inclusive). Return an array answer of length n where answer[i] is the total number of seats reserved for flight i + 1.

This is LeetCode 1109: Corporate Flight Bookings, a medium problem that is a direct application of the difference array technique. Instead of updating every flight in each booking's range, you mark only the boundaries of each range. A single prefix sum pass then reconstructs the full answer.

Why this problem matters

Corporate Flight Bookings is one of the purest examples of the difference array pattern. The naive approach would loop through each booking and add seats to every flight in the range [first, last]. If you have m bookings and the average range length is k, that brute force costs O(m * k), which can be as bad as O(m * n). The difference array brings this down to O(m + n).

The technique shows up repeatedly across LeetCode. Car pooling, range sum queries, meeting room scheduling, and any problem involving bulk range updates all use the same idea. Once you learn it here, you can apply it instantly to those problems too.

The key mental model is this: instead of painting every cell in a range, you place a "start marker" and an "end marker." Then you sweep through once and let the markers tell you the current total. It is the discrete analog of the sweep line technique.

The key insight

For each booking [first, last, seats], you only need two operations on a difference array diff:

• Add +seats at index first - 1 (converting to 0-indexed)
• Subtract -seats at index last (if last is less than n)

The subtraction at last (not last + 1) is because flights are 1-indexed and the range is inclusive. When you convert to 0-indexed, first - 1 is the start and last is one past the end.

After processing all bookings, a prefix sum over the difference array gives you the total reserved seats for each flight. The running sum at index i equals the total seats for flight i + 1.

The solution

def corpFlightBookings(bookings, n):
    diff = [0] * (n + 1)
    for first, last, seats in bookings:
        diff[first - 1] += seats
        if last < n:
            diff[last] -= seats
    result = []
    running = 0
    for i in range(n):
        running += diff[i]
        result.append(running)
    return result

The solution has two clear phases. First, you build the difference array by looping through every booking and recording the +seats and -seats at the appropriate indices. Second, you sweep through the first n entries computing a running sum. That running sum at each position is the answer for that flight.

Notice the if last < n guard. When a booking extends to the last flight (flight n), there is no need to subtract because there are no flights after it. The extra slot at index n in the array handles this gracefully, but checking explicitly keeps the intent clear.

Visual walkthrough

The walkthrough uses bookings = [[1,2,10],[2,3,20],[2,5,25]] with n = 5. After processing all three bookings into the difference array, the prefix sum produces [10, 55, 45, 25, 25]. Flight 2 has the most seats because all three bookings overlap there.

Complexity analysis

Time: O(m + n) where m is the number of bookings and n is the number of flights. You iterate through all m bookings to build the difference array (O(m)), then sweep through n entries to compute prefix sums (O(n)).

Space: O(n) for the difference array and the result array. Each booking is processed in constant space.

The building blocks

1. Difference array for range updates

The difference array is a technique for applying range updates in O(1) per update. Instead of modifying every element in a range, you modify only the endpoints:

diff[start] += value
diff[end + 1] -= value

After all updates, a prefix sum over diff gives you the actual values. This is the core building block behind corporate flight bookings, car pooling, and any problem where you need to add a constant to a contiguous subarray many times.

2. Prefix sum reconstruction

The prefix sum converts the difference array back into actual counts:

running = 0
for i in range(n):
    running += diff[i]
    result.append(running)

At each step, running holds the sum of all differences up to that index, which equals the total number of reserved seats for that flight. The prefix sum is one of the most versatile building blocks in algorithm problems, appearing in subarray sums, range queries, and cumulative statistics.

Edge cases

• Single booking spanning all flights: bookings = [[1,n,100]] means every flight gets 100 seats. The diff array has +100 at index 0 and no subtraction since last == n.
• Multiple bookings on the same flight: overlapping ranges accumulate naturally in the difference array. Two bookings adding 10 and 20 to flight 3 both contribute their +seats at the corresponding index.
• Booking of length 1: [3,3,15] means only flight 3 gets 15 seats. The diff array gets +15 at index 2 and -15 at index 3. The prefix sum correctly adds 15 only at that one position.
• All bookings overlap completely: if every booking covers flights 1 through n, the only nonzero entry in the diff array is at index 0. The prefix sum carries that total across all flights.
• n = 1: a single flight. Each booking contributes its seats to the only flight, and the diff array has just two slots.

From understanding to recall

You have seen the difference array solution and it makes sense. Two lines to build the array, one loop to sweep. But the details matter: subtracting at last (0-indexed, one past the inclusive end), handling the case when last == n, and converting between 1-indexed flights and 0-indexed array positions.

Under interview pressure, these small decisions are where mistakes happen. You might second-guess whether to subtract at last or last - 1. You might forget the 1-indexed to 0-indexed conversion. Spaced repetition removes that uncertainty. After a few rounds of writing the solution from scratch, the index arithmetic becomes automatic.

The difference array is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning it in isolation and drilling it with spaced repetition is far more effective than encountering it once inside a problem and hoping you remember it months later.

Related posts

• Car Pooling - Same difference array technique applied to tracking passengers at stops along a route
• Range Sum Query Immutable - Prefix sums for fast range queries, the read-side counterpart to the difference array's write-side optimization
• Subarray Sum Equals K - Prefix sums combined with a hash map to count subarrays with a target sum

CodeBricks breaks the corporate flight bookings LeetCode problem into its difference array and prefix sum building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a range update question comes up in your interview, you do not hesitate. You just write it.