LeetCode 1109 - Corporate Flight Bookings

The problem is asking us to compute the total number of seats reserved for each flight given a list of flight bookings. Each booking specifies a range of consecutive flights [firsti, lasti] and the number of seats seatsi reserved for each flight in that range.

leetcodemediumarrayprefix-sum

LeetCode Problem 1109

Difficulty: 🟡 Medium
Topics: Array, Prefix Sum

Solution

Problem Understanding

The problem is asking us to compute the total number of seats reserved for each flight given a list of flight bookings. Each booking specifies a range of consecutive flights [firsti, lasti] and the number of seats seatsi reserved for each flight in that range. The flights are numbered from 1 to n, and the result should be an array answer of length n, where answer[i] represents the total seats booked for flight i+1.

The input bookings can be thought of as a set of "range updates": each booking adds a fixed number of seats to a contiguous range of flights. The challenge is to efficiently process multiple overlapping bookings without iterating through every flight in every booking, which could be too slow for large inputs.

Constraints tell us that n and bookings.length can be up to 20,000, so a naive solution that iterates over the flights for every booking could reach 400 million operations, which is too slow. The input guarantees that all indices are valid (1 <= firsti <= lasti <= n) and the number of seats is always positive, so we do not have to handle invalid bookings or negative values.

Important edge cases include bookings that cover a single flight, bookings that cover the entire range of flights, multiple overlapping bookings, and bookings that start or end at the boundary flights.

Approaches

The brute-force approach iterates over each booking and updates the number of seats for every flight in the specified range. This guarantees correctness because it directly applies the seat reservations, but it is inefficient. For each booking [first, last, seats], it performs (last - first + 1) operations. In the worst case, this leads to a time complexity of O(n * m), where m is the number of bookings, which can be up to 400 million operations for maximum input sizes.

The optimal approach leverages the prefix sum trick, a common technique for efficiently applying range updates. Instead of updating every element in the range for each booking, we mark the start of the range with +seatsi and the position after the end of the range with -seatsi. After processing all bookings, a single prefix sum pass converts these markers into the total seats for each flight. This reduces the time complexity to O(n + m), which is feasible for the given constraints.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m) O(n) Directly updates each flight in every booking range
Optimal O(n + m) O(n) Uses prefix sum technique to apply range updates efficiently

Algorithm Walkthrough

  1. Initialize an array res of length n with all zeros. This array will eventually hold the total seats for each flight.
  2. Iterate over each booking [first, last, seats] in bookings. For each booking, increment res[first-1] by seats to mark the start of the booking range. If last < n, decrement res[last] by seats to mark the end of the booking range.
  3. After all bookings have been processed, iterate through res from index 1 to n-1, updating each element to be the sum of itself and the previous element. This computes the prefix sum, converting the range markers into actual seat totals.
  4. Return the final res array.

Why it works: The +seatsi at the start index and -seatsi after the end index create a difference array. Applying the prefix sum ensures that all flights in the range [first, last] accumulate seatsi, while flights outside the range remain unaffected. This guarantees correctness while reducing unnecessary updates.

Python Solution

from typing import List

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

The Python implementation first initializes a zero array for all flights. It then processes each booking by marking the start and end of the booking in the array. The prefix sum loop propagates the seat counts across the ranges efficiently, producing the final result.

Go Solution

func corpFlightBookings(bookings [][]int, n int) []int {
    res := make([]int, n)
    for _, booking := range bookings {
        first, last, seats := booking[0], booking[1], booking[2]
        res[first-1] += seats
        if last < n {
            res[last] -= seats
        }
    }
    for i := 1; i < n; i++ {
        res[i] += res[i-1]
    }
    return res
}

In Go, we initialize a slice res of length n. The approach mirrors Python: we apply the difference array technique and then a prefix sum. Go requires explicit slice creation and integer indexing, but the logic remains the same. There is no need to handle nil because make([]int, n) always returns a properly sized slice.

Worked Examples

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

Step Action res Array
Init res = [0,0,0,0,0] [0,0,0,0,0]
Booking 1 add 10 to res[0], subtract 10 from res[2] [10,0,-10,0,0]
Booking 2 add 20 to res[1], subtract 20 from res[3] [10,20,-10,-20,0]
Booking 3 add 25 to res[1], subtract 25 from res[5] (ignored) [10,45,-10,-20,0]
Prefix sum compute cumulative sums [10,55,45,25,25]

Example 2: bookings = [[1,2,10],[2,2,15]], n = 2

Step Action res Array
Init [0,0] [0,0]
Booking 1 add 10 to res[0], subtract 10 from res[2] (ignored) [10,0]
Booking 2 add 15 to res[1], subtract 15 from res[2] (ignored) [10,15]
Prefix sum [10,25] [10,25]

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) We process each booking once (O(m)) and compute prefix sums once (O(n))
Space O(n) We store one array of length n for the result

The optimal solution is linear in both the number of flights and the number of bookings, making it suitable for large input sizes up to 20,000.

Test Cases

# Provided examples
assert Solution().corpFlightBookings([[1,2,10],[2,3,20],[2,5,25]], 5) == [10,55,45,25,25]  # Example 1
assert Solution().corpFlightBookings([[1,2,10],[2,2,15]], 2) == [10,25]  # Example 2

# Edge cases
assert Solution().corpFlightBookings([[1,1,5]], 1) == [5]  # Single flight
assert Solution().corpFlightBookings([[1,5,1]], 5) == [1,1,1,1,1]  # Full range booking
assert Solution().corpFlightBookings([[1,3,10],[2,5,5],[3,3,2]], 5) == [10,15,17,5,5]  # Multiple overlaps
assert Solution().corpFlightBookings([], 3) == [0,0,0]  # No bookings
assert Solution().corpFlightBookings([[2,2,10]], 5) == [0,10,0,0,0]  # Single flight in the middle
Test Why
Example 1 Standard case with overlapping ranges
Example 2 Small input with overlapping bookings on a single flight
Single flight Minimal input size
Full range booking Booking covers all flights
Multiple overlaps Tests correct aggregation of overlapping bookings
No bookings Edge case, should return all zeros
Single middle flight Booking not at boundaries

Edge Cases

One edge case is a booking that covers only the first flight. This tests whether the implementation correctly handles array indexing at the start. The algorithm adds the seat count to the first element and handles the prefix sum properly.

Another edge case is a booking that covers the last flight. This tests whether we correctly avoid subtracting beyond the array bounds. Our implementation checks if last < n before decrementing, ensuring safety.

A third edge case is multiple overlapping bookings that cover the