Watch 10 video solutions for Corporate Flight Bookings, a medium level problem involving Array, Prefix Sum. This walkthrough by Kelvin Chandra has 2,643 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There are n flights that are labeled from 1 to n.
You are given an array of flight bookings bookings, where bookings[i] = [firsti, lasti, seatsi] represents a booking for flights firsti through lasti (inclusive) with seatsi seats reserved for each flight in the range.
Return an array answer of length n, where answer[i] is the total number of seats reserved for flight i.
Example 1:
Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5 Output: [10,55,45,25,25] Explanation: Flight labels: 1 2 3 4 5 Booking 1 reserved: 10 10 Booking 2 reserved: 20 20 Booking 3 reserved: 25 25 25 25 Total seats: 10 55 45 25 25 Hence, answer = [10,55,45,25,25]
Example 2:
Input: bookings = [[1,2,10],[2,2,15]], n = 2 Output: [10,25] Explanation: Flight labels: 1 2 Booking 1 reserved: 10 10 Booking 2 reserved: 15 Total seats: 10 25 Hence, answer = [10,25]
Constraints:
1 <= n <= 2 * 1041 <= bookings.length <= 2 * 104bookings[i].length == 31 <= firsti <= lasti <= n1 <= seatsi <= 104Problem Overview: You receive booking operations where each entry [first, last, seats] adds seats to every flight from first to last. With n flights and multiple bookings, the goal is to compute the final number of seats reserved for each flight efficiently.
Approach 1: Direct Array Manipulation (Time: O(m * n), Space: O(n))
Create an array of size n to store seat counts for each flight. For every booking, iterate from first to last and add the number of seats to each position in the array. This approach mirrors the booking definition directly: process each range and update every affected flight. While simple to implement, it becomes expensive when bookings span large ranges or when both n and m are large. The repeated range updates make it inefficient compared to prefix-based techniques often used with array problems.
Approach 2: Difference Array Technique (Time: O(n + m), Space: O(n))
Instead of updating every flight inside a booking range, mark only the boundaries. Add seats at index first - 1 and subtract seats at index last (if it exists). This creates a difference array that represents how seat counts change between indices. After processing all bookings, compute a running prefix sum across the array to recover the final seat counts for each flight. This technique converts multiple range updates into constant-time boundary updates and a single linear pass using a prefix sum. The result reduces the complexity dramatically from repeated updates to a single accumulation pass.
Recommended for interviews: Interviewers expect the Difference Array or Prefix Sum approach. The brute force range update demonstrates baseline reasoning, but the boundary-marking trick shows you understand how to optimize repeated range operations in array problems. The optimal solution runs in O(n + m) time and scales cleanly even when bookings cover large flight ranges.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Array Manipulation | O(m * n) | O(n) | Small inputs or when implementing a straightforward range update without optimization |
| Difference Array Technique | O(n + m) | O(n) | Large booking ranges or many updates where efficient range processing is required |