Corporate Flight Bookings — Medium Problem & Solution

Problem statement

There are n flights numbered 1 to n. bookings[i] = [first, last, seats] means seats seats were reserved on every flight from first to last inclusive.

Return an array where entry i is the total number of seats reserved on flight i + 1.

Example 1

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

Example 2

Input: bookings = [[1,2,10],[2,2,15]], n = 2
Output: [10,25]

Example 3

Input: bookings = [[1,1,5]], n = 3
Output: [5,0,0]

Constraints

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

How to solve Corporate Flight Bookings

A difference array. Each booking touches a contiguous range, so record +seats at its start and -seats one past its end; a prefix sum over those deltas then yields every flight's total in one pass.

Approach

1. Create diff of length n + 1, all zeros.
2. For each booking, do diff[first - 1] += seats and diff[last] -= seats.
3. Sweep a running total across diff, writing it into the output.

Why it works

The trick is that a range update is two point updates on the derivative — the cost of a booking becomes O(1) regardless of how many flights it spans. The +1 slot is what lets a booking ending at flight n subtract somewhere harmless instead of running off the array.

Complexity

• Time — O(bookings + n)
• Space — O(n)

Pitfalls

• Flights are 1-indexed, so the start offset is first - 1.
• The subtraction goes at last, not last - 1 — the range is inclusive.
• diff needs one extra slot for bookings that end on the last flight.

Reference solution

Python

from typing import List

def corpFlightBookings(bookings: List[List[int]], n: int) -> List[int]:
    diff = [0] * (n + 1)
    for first, last, seats in bookings:
        diff[first - 1] += seats
        diff[last] -= seats
    out = []
    running = 0
    for i in range(n):
        running += diff[i]
        out.append(running)
    return out

JavaScript

var corpFlightBookings = function(bookings, n) {
    var diff = [], i;
    for (i = 0; i <= n; i++) diff.push(0);
    for (i = 0; i < bookings.length; i++) {
        diff[bookings[i][0] - 1] += bookings[i][2];
        diff[bookings[i][1]] -= bookings[i][2];
    }
    var out = [], running = 0;
    for (i = 0; i < n; i++) {
        running += diff[i];
        out.push(running);
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Minimum Number of Increments on Subarrays to Form a Target Array Medium
• Find the Winner of an Array Game Medium
• Queries on a Permutation With Key Medium
• Find the Winner of the Circular Game Medium
• Longest Subsequence With Limited Sum Medium
• Partition Array for Maximum Sum Medium