Corporate Flight Bookings
Problem
Given a list of flight bookings where each booking specifies a range of flights and the number of seats booked for each flight in that range, return an array representing the total seats booked for each flight from 1 to n.
- 1 ≤ n ≤ 2 * 10⁴
- 1 ≤ bookings.length ≤ 2 * 10⁴
- bookings[i].length == 3
- 1 ≤ first_i ≤ last_i ≤ n
- 1 ≤ seats_i ≤ 10⁴
Example
bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5[10,55,45,25,25]The brute-force approach would add seats_i to every flight from first_i to last_i for each booking, resulting in O(n*m) time where m is the number of bookings. This is inefficient for large inputs. The key insight is to use a difference array to record the net changes at the boundaries of each booking range. For the example, after processing all bookings, the difference array captures increments at the start indices and decrements just after the end indices. A prefix sum over this difference array reconstructs the total seats booked per flight efficiently.
Approach
Straightforward Solution
A naive approach iterates over each booking and adds seats_i to every flight in the range [first_i, last_i], resulting in O(n*m) time complexity, which is too slow for large inputs.
Core Observation
Each booking adds seats to a contiguous range of flights. Instead of updating every flight in the range, the problem can be transformed by recording only the net seat changes at the boundaries of each range, enabling efficient cumulative calculation.
Path to Optimal
PreviewThe key recognition signals are 'range updates' and 'query for final values after all updates'. These indicate the use of a difference array or prefix sum technique because it allows O(1) updates per booking and a single O(n) pass to compute final results…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewInitialize an array of zeros representing flights. For each booking, increment the start index by seats and decrement the position after the end index by seats if it exists…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n + m)
Each booking is processed in O(1) time by updating two positions in the difference array. Then, a single pass of length n computes the prefix sums, resulting in O(n + m) total time.
Space
O(n)
An auxiliary array of length n is used to store the difference array and final results. This space is necessary to represent the seat counts for all flights.
Pattern Spotlight
Prefix Sum (Difference Array for Range Updates)
When multiple range updates are applied and the final values are queried, record only the net changes at range boundaries and reconstruct the final array with a single prefix sum pass to achieve efficient updates.
Solution
| 1 | class Solution: |
| 2 | def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]: |
| 3 | flights = [0] * n |
| 4 | |
| 5 | for first, last, seats in bookings: |
| 6 | flights[first - 1] += seats |
| 7 | if last < n: |
| 8 | flights[last] -= seats |
| 9 | |
| 10 | for i in range(1, n): |
| 11 | flights[i] += flights[i - 1] |
| 12 | |
| 13 | return flights |
Step-by-Step Solution
Apply Range Updates Using Difference Array Technique
| 3 | flights = [0] * n |
| 5 | for first, last, seats in bookings: |
| 6 | flights[first - 1] += seats |
| 7 | if last < n: |
| 8 | flights[last] -= seats |
Objective
To record net seat changes at the start and end boundaries of each booking range efficiently.
Key Insight
Instead of adding seats to every flight in the booking range, incrementing the start index and decrementing the position after the end index captures the effect of the booking as a net change. This reduces multiple range updates to constant time operations per booking, enabling efficient aggregation later.
Interview Quick-Check
Core Logic
Increment flights[first - 1] by seats to mark the start of the booking range and decrement flights[last] by seats if last < n to mark the end boundary.
Common Pitfalls & Bugs
Forgetting to check if last < n before decrementing flights[last] can cause index errors or incorrect results.
State & Boundaries
The difference array stores net changes, not final values, so it must be processed with a prefix sum to obtain the final seat counts.
Compute Prefix Sum to Aggregate Final Seat Counts
To transform the difference array into the final array of total seats booked per flight by accumulating net changes.
Return the Final Aggregated Seat Counts
To output the computed array representing total seats booked for each flight.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
flights[first - 1] += seatsIncrement the start index of the booking range by the number of seats booked.
This marks the beginning of the range where seats are added, capturing the net increase for all subsequent flights until the end of the range.
flights[last] -= seatsDecrement the position immediately after the booking range by the number of seats booked.
This cancels out the increment beyond the booking range, ensuring only flights within the range accumulate the seats after prefix sum computation.
flights[i] += flights[i - 1]Add the seat count of the previous flight to the current flight.
This cumulative addition applies all prior bookings to the current flight, completing the transformation from difference array to final results.
Full line-by-line criticality + rationale for all 8 lines available on Pro.
Test Your Understanding
Why does incrementing at the start index and decrementing just after the end index correctly represent the range updates?
See the answer with Pro.
Related Problems
Prefix Sum pattern
Don't just read it. Drill it.
Reconstruct Corporate Flight Bookings from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Corporate Flight Bookings drill