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.
This approach involves updating a direct array for each booking. We simply iterate over each booking, updating the flights within the specified range. This approach is straightforward but could be inefficient for large inputs due to repeated updates.
This C solution uses calloc to zero-initialize the answer array of size n. It then loops through each booking, and for each booking, it loops through the range of flights affected by the booking, updating the answer array by adding the booked seats.
Time Complexity: O(n * m) where n is the number of flights and m is the number of bookings.
Space Complexity: O(n) for storing the result.
To optimize the update operations, we can employ a difference array. By storing the increment at the start of the range and the decrement right after the end of the range, we can later use prefix sums to compute the final result. This reduces the time complexity significantly for processing each booking.
The C solution uses a difference array to store the net effect of each booking. We increment at the start index and decrement right after the end index. Then we compute the prefix sums to get the final result.
Time Complexity: O(n + m) where n is the number of flights and m is the number of bookings.
Space Complexity: O(n) for storing the result and additional space used by the difference array.
We notice that each booking is for seats seats on all flights within a certain interval [first, last]. Therefore, we can use the idea of a difference array. For each booking, we add seats to the number at the first position and subtract seats from the number at the last + 1 position. Finally, we calculate the prefix sum of the difference array to get the total number of seats booked for each flight.
The time complexity is O(n), where n is the number of flights. Ignoring the space consumption of the answer, the space complexity is O(1).
We can also use a binary indexed tree, combined with the idea of difference, to implement the above operations. We can consider each booking as booking seats seats on all flights within a certain interval [first, last]. Therefore, for each booking, we add seats to the first position of the binary indexed tree and subtract seats from the last + 1 position of the binary indexed tree. Finally, we calculate the prefix sum for each position in the binary indexed tree to get the total number of seats booked for each flight.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the number of flights.
Here is a basic introduction to the binary indexed tree:
A binary indexed tree, also known as a "Binary Indexed Tree" or Fenwick tree. It can efficiently implement the following two operations:
update(x, delta): Add a value delta to the number at position x in the sequence;query(x): Query the interval sum of the sequence [1,...x], that is, the prefix sum of position x.The time complexity of these two operations is O(log n).
| Approach | Complexity |
|---|---|
| Approach 1: Direct Array Manipulation | Time Complexity: O(n * m) where n is the number of flights and m is the number of bookings. |
| Approach 2: Difference Array Technique | Time Complexity: O(n + m) where n is the number of flights and m is the number of bookings. |
| Difference Array | — |
| Binary Indexed Tree + Difference Idea | — |
| 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 |
1109. Corporate Flight Bookings (LeetCode Weekly Contest 144) • Kelvin Chandra • 2,643 views views
Watch 9 more video solutions →Practice Corporate Flight Bookings with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor