There are n flights labeled from 1 to n. You are given an array of flight bookings where bookings[i] = [firsti, lasti, seatsi] represents a booking for flights firsti through lasti (inclusive) with seatsi seats reserved for each flight in that range.

Return an array answer of length n, where answer[i] is the total number of seats reserved for flight i + 1.

Examples

Example 1:

Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
Output: [10,55,45,25,25]
Explanation:
Flight 1: 10 seats
Flight 2: 10 + 20 + 25 = 55 seats
Flight 3: 20 + 25 = 45 seats
Flight 4: 25 seats
Flight 5: 25 seats

Example 2:

Input: bookings = [[1,2,10],[2,2,15]], n = 2
Output: [10,25]
Explanation:
Flight 1: 10 seats
Flight 2: 10 + 15 = 25 seats

Constraints

  • 1 <= n <= 2 * 10^4
  • 1 <= bookings.length <= 2 * 10^4
  • 1 <= firsti <= lasti <= n
  • 1 <= seatsi <= 10^4

Intro: Partial Sum and Difference Array

Partial sum (prefix sum)

  • Idea: For an array A, the partial sum at index i is S[i] = A[0] + A[1] + ... + A[i]. Then the sum of any contiguous segment [l, r] is S[r] - S[l-1] (with S[-1] = 0).
  • Use: Range-sum queries in O(1) after O(n) preprocessing; also the basis for many “subarray sum” problems.

Difference array (range update trick)

  • Idea: Instead of updating every index in [l, r] by +d, we can:
    • Add d at index l
    • Subtract d at index r+1 (if in bounds) Then one prefix sum over this “difference” array recovers the actual values after all range updates.
  • Why it works: Prefix sum at i equals the sum of all “+d” and “-d” that affect position i; that sum is exactly the total change for position i.

C++ std::partial_sum

From <numeric>:

// Computes prefix sums in-place: out[i] = in[0] + in[1] + ... + in[i]
partial_sum(first, last, d_first);

// With custom binary op (e.g. multiply): out[i] = in[0] * in[1] * ... * in[i]
partial_sum(first, last, d_first, std::multiplies<>());

For this problem we build a difference array (add at first, subtract at last+1), then run partial_sum or inclusive_scan (C++17) to get the final seat counts.

Common LeetCode problems using partial sum / difference array

Thinking Process

  1. Difference array turns “add d to [l, r]” into two point updates: +d at l, -d at r+1.
  • Clarify if the array is sorted, has negatives, or allows duplicates.
  • Prefix sums answer range queries; hash maps answer pair/count queries.
  • In-place tricks use swap/write index instead of extra arrays.
Array + hash map 2 7 11 map hash map for O(1) lookups

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Prefix sum (this problem) O(n) O(n) Range queries, subarray sum
Sort + scan O(n log n) O(1) Intervals, meeting rooms
Kadane’s algorithm O(n) O(1) Maximum subarray
Hash map counting O(n) O(n) Frequency, two-sum variants

Solution

For each booking, add seats to every flight in [first, last].

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> rtn(n);
        for (auto& booking : bookings) {
            int left = booking[0] - 1, right = booking[1] - 1, seats = booking[2];
            while (left <= right) {
                rtn[left++] += seats;
            }
        }
        return rtn;
    }
};

Solution Explanation

Approach: Prefix sum (this problem)

Key idea: 1. Difference array turns “add d to [l, r]” into two point updates: +d at l, -d at r+1.

How the code works:

  1. Difference array turns “add d to [l, r]” into two point updates: +d at l, -d at r+1.
    • Clarify if the array is sorted, has negatives, or allows duplicates.
    • Prefix sums answer range queries; hash maps answer pair/count queries.
    • In-place tricks use swap/write index instead of extra arrays.

Walkthrough — input bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5, expected output [10,55,45,25,25]:

Flight 1: 10 seats Flight 2: 10 + 20 + 25 = 55 seats Flight 3: 20 + 25 = 45 seats Flight 4: 25 seats Flight 5: 25 seats

Time: O(m × L), where m = bookings.length, L = average range length (worst O(n)). · Space: O(n).

Complexity Comparison

Approach Time Space
Brute force (range loop) O(m × L) O(n)
Difference + partial_sum / inclusive_scan O(n + m) O(n)

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Key Takeaways

  1. Difference array turns “add d to [l, r]” into two point updates: +d at l, -d at r+1.
  2. Prefix sum over the difference array recovers the final value at each index.
  3. C++ partial_sum or inclusive_scan (C++17) compute prefix sums in one line; inclusive_scan can use execution policies for parallel scan.
  4. Same pattern appears in Car Pooling (1094) and other “range update, single query pass” problems.

References

Template Reference