#1109

Medium

LeetCode Problem Workspace

Corporate Flight Bookings

Solve Corporate Flight Bookings by marking range changes once, then building final seat totals with a single prefix sum pass.

array prefix sum

Problem Statement

You have flights labeled from 1 through n, and each booking applies the same seat reservation count to every flight in an inclusive interval. For a booking [first, last, seats], each flight from first to last must gain seats in its final total.

Your job is to return an array of length n where each position stores the total reserved seats for that flight label. In the sample bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5, flight 2 collects seats from all three ranges, which is why the final result becomes [10,55,45,25,25].

Examples

Example 1

Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5

Output: [10,55,45,25,25]

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]

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 * 104
1 <= bookings.length <= 2 * 104
bookings[i].length == 3
1 <= firsti <= lasti <= n
1 <= seatsi <= 104

Solution Approach

Brute force range addition

The most direct idea is to loop through every booking and add seats to every flight index from first to last. This matches the problem statement exactly, but it repeats work heavily when long booking ranges overlap. In Corporate Flight Bookings, that repeated inner loop is the reason a naive array approach can time out.

Difference array for range boundaries

Instead of filling every seat contribution immediately, record only the range boundaries. Add seats at first - 1, and subtract seats at last if last is still inside the array. That means each booking in Corporate Flight Bookings becomes O(1): mark where the reservation starts affecting flights and where that effect ends.

Prefix sum to rebuild final seat counts

After all bookings are marked, sweep left to right and accumulate the running total. That prefix sum converts the difference array back into the real reserved seat count for each flight. This is the key pattern here: range updates first, then one reconstruction pass, which turns many overlapping booking intervals into an O(bookings.length + n) solution.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The brute force version takes O(m * n) in the worst case when many bookings span large parts of the flight list, where m is bookings.length. The optimal Corporate Flight Bookings solution uses a difference array plus one prefix sum, so each booking is handled in O(1) and the rebuild pass over n flights is O(n), for total time O(m + n). Space is O(n) for the working array that stores boundary changes and then the final seat totals.

What Interviewers Usually Probe

The interviewer emphasizes inclusive ranges, which usually hints that you should mark start and stop points instead of updating every flight directly.
They ask whether you can do better than touching every index inside each booking range, pointing toward a difference array optimization.
They care about overlapping bookings and final per-flight totals, which is a strong signal for range updates followed by a prefix sum rebuild.

Common Pitfalls or Variants

Common pitfalls

Forgetting the 1-based flight labels and writing updates as if the array were already 0-based, which shifts every reservation.
Subtracting at last - 1 instead of last when ending a booking range, which breaks the inclusive boundary for Corporate Flight Bookings.
Trying to prefix-sum before all booking markers are placed, which mixes partial state with final totals and hides boundary bugs.

Follow-up variants

Return the maximum reserved seats on any single flight after processing all bookings, which still comes from the same rebuilt prefix array.
Support cancellation records with negative seat values, where the same difference array pattern still works as long as updates are applied correctly.
Answer seat totals after each incremental booking batch, which may push the discussion toward repeated prefix rebuilds or a more dynamic range update structure.

FAQ

What is the key pattern in Corporate Flight Bookings?

The core pattern is difference array plus prefix sum. Each booking updates only the start and end boundary, and one running sum pass converts those markers into the final seat totals for every flight.

Why is the brute force solution too slow for this problem?

Because one booking can cover many flights, a direct loop from first to last for every booking repeats work across overlapping ranges. In the worst case, Corporate Flight Bookings becomes much slower than necessary when many intervals are long.

Why do we subtract at last instead of last - 1 in the optimized solution?

The booking range is inclusive, so the added seats must still apply to flight last. Subtracting at index last in 0-based storage means the running total stops only after that flight has been counted.

How does the sample produce [10,55,45,25,25]?

Booking [1,2,10] adds 10 to flights 1 and 2, booking [2,3,20] adds 20 to flights 2 and 3, and booking [2,5,25] adds 25 to flights 2 through 5. Summing per flight gives 10, 55, 45, 25, and 25.

Is prefix sum alone enough without a difference array?

Not for efficient updates in this problem. Prefix sum is the reconstruction step, but the real speedup in Corporate Flight Bookings comes from first storing each booking as boundary changes instead of updating every covered flight immediately.

terminal

Solution

Solution 1: 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.

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        ans = [0] * n
        for first, last, seats in bookings:
            ans[first - 1] += seats
            if last < n:
                ans[last] -= seats
        return list(accumulate(ans))

Solution 2: Binary Indexed Tree + Difference Idea

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.

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        ans = [0] * n
        for first, last, seats in bookings:
            ans[first - 1] += seats
            if last < n:
                ans[last] -= seats
        return list(accumulate(ans))

Continue Practicing

#1094 car pooling #1124 longest well performing interval #1140 stone game ii