Corporate Flight Bookings

Corporate Flight Bookings is the cleanest introduction to the difference array — a trick that turns "add the same value to a whole range" from an O(range) chore into just two writes, no matter how wide the range is.

The slow way first

The literal reading: for each booking, loop over every flight from first to last and add seats. That works, but if a booking covers a huge range you touch every flight in it, and with many wide bookings the total work blows up to O(n × bookings) — far too slow.

The question to ask: each booking changes a contiguous run by the same amount — can I record the change without walking the whole run? Yes. A range update is fully described by where it starts and where it stops, so we only need to mark those two endpoints.

The idea: store changes, not totals

Keep an array diff of deltas instead of totals. To add seats across flights first..last:

• diff[first - 1] += seats — "from here on, add seats."
• diff[last] -= seats — "and stop adding it after this flight."

Each booking is two writes, regardless of range width. Once every booking is recorded, walk diff left to right keeping a running prefix sum: the value at each position is that flight's true total. The -= seats at last exactly cancels the earlier += seats, so the bump only covers first..last.

We use n + 1 slots so a booking ending at flight n has a harmless overflow slot for its -= seats — that slot is never returned.

Walk through it

Step through the animation. For each booking the l pointer marks first - 1 (where seats are added) and the r+1 pointer marks last (where they are removed). After all three bookings, diff = [8, 10, -5, 0, -13]. Then the i pointer sweeps left to right, accumulating the running total so each cell becomes its flight total: [8, 18, 13, 13].

Pseudocode

make diff = array of n+1 zeros
for each booking [first, last, seats]:
    diff[first - 1] += seats        # start adding seats here
    diff[last]      -= seats        # stop adding them after "last"
running = 0
for i from 0 to n-1:
    running += diff[i]              # prefix sum = true total
    answer[i] = running
return answer

The Python solution

def corp_flight_bookings(bookings, n):
    diff = [0] * (n + 1)
    for first, last, seats in bookings:
        l = first - 1
        diff[l] += seats
        diff[last] -= seats
    answer = []
    running = 0
    for d in diff[:n]:
        running += d
        answer.append(running)
    return answer

• diff has n + 1 slots so the -= seats at last == n lands in a scratch slot we never return.
• For each booking, diff[l] += seats opens the bump at flight first and diff[last] -= seats closes it — two writes, range width irrelevant.
• Lines 5-6 are the whole trick: a range update done in O(1).
• The second loop is the prefix sum. running carries the accumulated effect of all bumps that are still open at this flight, so running is exactly that flight's total.
• We slice diff[:n] so the overflow slot is dropped from the answer.

Complexity

Each booking costs O(1) instead of O(range), and the final prefix-sum sweep is one pass over n. That trade — record only the endpoints of a range change, then prefix-sum once — is the core of the difference-array pattern.

When this pattern shows up

Practice