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
The 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. By incrementing seats at first_i - 1 and decrementing seats at last_i (if within bounds), the difference array captures the net effect of all bookings.
Optimal Approach
Initialize 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. Then, compute the prefix sum of this array to get the total seats booked per flight. This approach runs in O(n + m) time and O(n) space, efficiently handling large inputs.
Time
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 |
| 1 | import java.util.List; |
| 2 | |
| 3 | public class Solution { |
| 4 | public int[] corpFlightBookings(List<List<Integer>> bookings, int n) { |
| 5 | int[] flights = new int[n]; |
| 6 | |
| 7 | for (List<Integer> booking : bookings) { |
| 8 | int first = booking.get(0); |
| 9 | int last = booking.get(1); |
| 10 | int seats = booking.get(2); |
| 11 | |
| 12 | flights[first - 1] += seats; |
| 13 | if (last < n) { |
| 14 | flights[last] -= seats; |
| 15 | } |
| 16 | } |
| 17 | |
| 18 | for (int i = 1; i < n; i++) { |
| 19 | flights[i] += flights[i - 1]; |
| 20 | } |
| 21 | |
| 22 | return flights; |
| 23 | } |
| 24 | } |
| 1 | #include <vector> |
| 2 | |
| 3 | using namespace std; |
| 4 | |
| 5 | class Solution { |
| 6 | public: |
| 7 | vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) { |
| 8 | vector<int> flights(n, 0); |
| 9 | |
| 10 | for (const auto& booking : bookings) { |
| 11 | int first = booking[0]; |
| 12 | int last = booking[1]; |
| 13 | int seats = booking[2]; |
| 14 | |
| 15 | flights[first - 1] += seats; |
| 16 | if (last < n) { |
| 17 | flights[last] -= seats; |
| 18 | } |
| 19 | } |
| 20 | |
| 21 | for (int i = 1; i < n; ++i) { |
| 22 | flights[i] += flights[i - 1]; |
| 23 | } |
| 24 | |
| 25 | return flights; |
| 26 | } |
| 27 | }; |
| 1 | var corpFlightBookings = function(bookings, n) { |
| 2 | const flights = new Array(n).fill(0); |
| 3 | |
| 4 | for (const booking of bookings) { |
| 5 | const first = booking[0]; |
| 6 | const last = booking[1]; |
| 7 | const seats = booking[2]; |
| 8 | |
| 9 | flights[first - 1] += seats; |
| 10 | if (last < n) { |
| 11 | flights[last] -= seats; |
| 12 | } |
| 13 | } |
| 14 | |
| 15 | for (let i = 1; i < n; i++) { |
| 16 | flights[i] += flights[i - 1]; |
| 17 | } |
| 18 | |
| 19 | return flights; |
| 20 | }; |
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
| 10 | for i in range(1, n): |
| 11 | flights[i] += flights[i - 1] |
Objective
To transform the difference array into the final array of total seats booked per flight by accumulating net changes.
Key Insight
The prefix sum accumulates all net changes up to each flight index, effectively applying all range updates in order. This step converts the difference array representation into the actual seat counts per flight.
Interview Quick-Check
Core Logic
Iterate from the second flight to the last, adding the previous flight's seat count to the current to accumulate all prior bookings.
State & Boundaries
Start the prefix sum from index 1 since index 0 is the base case with no prior flights.
Complexity
This single pass over the flights array runs in O(n) time, ensuring overall efficiency.
Return the Final Aggregated Seat Counts
| 13 | return flights |
Objective
To output the computed array representing total seats booked for each flight.
Key Insight
After applying all range updates and computing the prefix sums, the flights array holds the correct total seats booked per flight, ready to be returned as the final answer.
Interview Quick-Check
Core Logic
Return the flights array after prefix sum aggregation as the final result.
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.
flights = [0] * nInitialize an array of zeros to represent seat bookings for each flight.
This array serves as a difference array to efficiently record net seat changes at flight boundaries, enabling O(1) updates per booking.
if last < n:Check if the end index is within the flights array bounds.
Ensuring the end index is valid prevents out-of-bounds errors when decrementing the position after the booking range.
for i in range(1, n):Iterate through flights from the second flight to the last to compute prefix sums.
This loop accumulates all net changes recorded in the difference array, converting it into the final seat counts per flight.
for first, last, seats in bookings:Iterate over each booking to apply range updates.
Processing each booking individually allows the algorithm to record net changes without updating every flight in the range, which would be inefficient.
return flightsReturn the array containing total seats booked for each flight.
After prefix sum aggregation, this array accurately reflects the total seats booked per flight as required by the problem.
Test Your Understanding
Why does incrementing at the start index and decrementing just after the end index correctly represent the range updates?
Because the increment at the start index adds seats to all subsequent flights, and the decrement at the position after the end index cancels out the addition beyond the booking range, ensuring only flights within the range accumulate the seats when prefix sums are computed.
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