1109. Corporate Flight Bookings

1109

MediumPrefix Sum and Difference ArrayDifference array + prefix sumRange-update via difference array

Corporate Flight Bookings

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

Open official problem prompt ↗

In plain English

Compute the total seats reserved for each of the n flights after applying many overlapping range reservations, without re-touching every flight for every booking.

Picture it like this

Think of a ledger of guests entering and leaving a party. Rather than counting the crowd every minute, you mark '+k at time they arrive, -k when they leave', then walk the timeline once to know how many people are present at each moment.

Example

Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
Output: [10, 55, 45, 25, 25]
Why: Flight 2 gets 10 + 20 + 25 = 55 seats from all three bookings; the others sum their overlapping bookings the same way.

Constraints

1 <= n <= 2 * 10^41 <= bookings.length <= 2 * 10^4bookings[i].length == 31 <= first_i <= last_i <= n1 <= seats_i <= 10^4

Pattern lesson

See the pattern, then code

Range-update via difference array

↗

Prefix Sum and Difference Array

Repeated range queries, subarray totals, balanced counts, or batched range updates.. Instead of touching every index in a range, record only where the added amount starts and where it stops: +seats at first, -seats just past last. A prefix sum then reconstructs the true value at every flight in one pass.

New words, made simpleKnow these before the algorithm

Difference array: An auxiliary array where diff[i] stores the change relative to diff[i-1]; its prefix sum rebuilds the original values.
Range update: Adding a fixed value to every element in a contiguous interval [l, r].
Prefix sum: A running total so that position i holds the sum of everything up to i.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Brute force per booking

With up to 2*10^4 bookings each spanning up to 2*10^4 flights, this is ~4*10^8 operations and risks TLE.

For each booking, loop from first to last and add seats to every flight in that range.

Time O(n * m)Space O(n)

Best choiceDifference array + prefix sum

Each booking costs O(1) to record and one linear sweep produces the answer.

Mark +seats at the range start and -seats one past the range end, then take one prefix-sum pass to materialize every flight's total.

Time O(n + m)Space O(n)

The rule we keep true

Invariant

After processing all bookings, the prefix sum of diff up to index i equals the total seats reserved for flight i + 1.

Why this is correct

Reasoning

Adding s at first-1 and subtracting s at last means the +s propagates through every prefix sum from flight first onward, while the -s cancels it starting at flight last+1. The net effect is exactly +s on flights first..last, which is what the booking specifies. Summed contributions of all bookings overlap correctly because addition is associative.

The algorithm in three movesSay these aloud before coding

1Create a diff array of size n + 1 initialized to zero

diff after all bookings = [10, 45, -10, -20, 0, -25]

2For each booking [first, last, seats], add seats at index first-1 and subtract seats at index last

prefix: 10 -> 55 -> 45 -> 25 -> 25

3Sweep left to right, accumulating a running sum

answer = [10, 55, 45, 25, 25]

4Append the running sum for each flight to the answer

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

100

451

-102

-203

-255

1 · Readfirst=1, last=2, seats=10

2 · AskWhere to mark the delta?

3 · Update statediff = [10, 0, -10, 0, 0, 0]

4 · Result+10 at index 0, -10 at index 2

Key takeaway

The difference array (0-indexed) after applying all three bookings, before the prefix-sum sweep.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Allocate the difference array
Size n + 1 so the -seats mark at index last never runs off the end even when last == n.
2
Lines 4-6Record each booking in O(1)
Convert the 1-indexed flight range to 0-indexed diff positions: +seats at first-1, -seats at last.
3
Lines 7-11Prefix-sum sweep
Accumulate running and emit it per flight to turn the deltas back into absolute seat totals.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A booking covering the entire range [1, n]
A single-flight booking where first == last
Multiple bookings that fully overlap on the same flights
n = 1 with one booking

Common beginner mistakes

Off-by-one from the 1-indexed flight labels: the start delta goes at first-1, not first
Subtracting at last+1 in 1-indexed terms equals subtracting at index last in 0-indexed terms; mixing the two conventions breaks the answer
Sizing diff as n instead of n + 1 and indexing out of bounds when last == n

Check your understanding

Why do we place the negative delta at index last (0-indexed) rather than last+1?

Corporate Flight Bookings

Corporate Flight Bookings

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Prefix Sum and Difference Array