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 <= 104The key challenge in #1109 Corporate Flight Bookings is efficiently applying multiple range updates to flight seats. A direct approach of updating every flight within each booking range would take O(n * m) time, which becomes inefficient when the number of bookings grows large.
A more optimal strategy uses the Prefix Sum (Difference Array) technique. Instead of updating every index within a range, you mark the start and end boundaries of the booking using a difference array. Specifically, add the seat value at the starting flight index and subtract it right after the ending index. After processing all bookings, compute a prefix sum over the array to accumulate the final seat counts for each flight.
This approach significantly reduces the time complexity because each booking is processed in constant time, followed by a single pass to build the final results. It’s a classic example of using prefix sums to optimize repeated range updates.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Naive Range Update | O(n * m) | O(n) |
| Prefix Sum / Difference Array | O(n + m) | O(n) |
NeetCodeIO
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of range update and prefix sum problems frequently appear in technical interviews at large tech companies. This problem tests understanding of optimization techniques and array manipulation patterns.
An array combined with the difference array technique works best for this problem. It allows efficient range updates and a final prefix sum computation to derive the total bookings for each flight.
The optimal approach uses a prefix sum technique with a difference array. Instead of updating every element in a booking range, you mark only the start and end boundaries and compute the final values with a prefix sum pass. This reduces the time complexity to O(n + m).
The prefix sum technique efficiently handles multiple range updates without repeatedly modifying each index. By marking changes at boundaries and later accumulating them, we avoid expensive nested loops.