Domain 2MediumMEDIUM

Corporate Flight Bookings

Uses difference array technique to handle range updates efficiently, reducing time complexity from O(N*K) to O(N+K).

Domain: medium•Updated: 2026-09-08
#difference array#prefix sum#O(N + K)#O(N)

Problem Breakdown

We are managing seat reservations for n flights labeled 1 through n. We receive a list of bookings, where each booking specifies an inclusive range [first, last] and the number of seats reserved (seats) for every flight in that range. Our goal is to compute the total accumulated seats reserved for each individual flight after processing all bookings.

Inputs:

  • bookings: A 2D list (list of lists) where each element [first, last, seats] defines a reservation.
  • n: An integer representing the number of flights.

Outputs:

  • answer: A list of length n, where index i corresponds to flight i+1. The value is the total seat count for that specific flight.

Constraints & Edge Cases:

  • Flights are 1-indexed in input, but we must return a standard Python array (0-indexed). We need to map flight k to index k-1.
  • Ranges can overlap significantly or be disjoint.
  • The maximum number of flights and bookings is 2⋅1042 \cdot 10^4. A naive simulation iterating through every booking range could result in up to (N/2)×N(N/2) \times N operations, potentially hitting Time Limit Exceeded (TLE). We need an efficient approach for large inputs.

Intuition

If we were to simulate the bookings directly on a frequency array of size n, each booking [first, last] would require iterating from index first-1 to last-1. In the worst case where every flight is booked in every range (e.g., all ranges are 1..N), this results in O(N⋅K)O(N \cdot K) time complexity. Given constraints of up to 20,00020,000 for both N and bookings count, (2⋅104)2=4⋅108(2\cdot 10^4)^2 = 4\cdot 10^8, which is risky for Python within typical interview limits (usually ~1-3 seconds).

Key Insight: This problem maps perfectly onto the Difference Array technique. Instead of updating every element in a range, we record changes at specific boundaries:

  1. Add seats to the start index (first - 1).
  2. Subtract seats from the index immediately following the end (last).

By doing this for all bookings and then computing the prefix sum (cumulative sum) of the array once, we recover the actual seat counts at each flight efficiently. This transforms range updates into O(1)O(1) operations per booking.

Approach

  1. Initialize a Difference Array: Create an integer list diff of size n + 2. We use n + 2 to safely handle the subtraction logic without boundary checks (specifically when a booking ends at flight n, we need index n+1 or simply ensure array is large enough).
    • For each booking [first, last, seats]:
      • Increment diff[first - 1] += seats.
      • Decrement diff[last] -= seats. Note: Since flights are up to n, the subtraction happens at index last (which corresponds to flight last+1). If we allocate size n + 2, indices go up to n + 1. This covers all cases safely.
  2. Compute Prefix Sums: Iterate through the difference array from index 0 to n - 1. Maintain a running sum (current_seats) and update it by adding the current value in diff[i]. Store this cumulative total into our result list (or overwrite diff if we don’t need original values).
  3. Return Result: Return the first n elements of the computed array, which represent flights 1 through n.

Complexity Analysis

  • Time Complexity: O(N+K)O(N + K), where NN is the number of flights and KK is the length of bookings. We iterate once over bookings (O(K)O(K)) to apply difference updates, then iterate once over the array size N+2N+2 (O(N)O(N)) to compute prefix sums. This fits well within limits for N=20,000N=20,000.
  • Space Complexity: O(N)O(N) to store the result/difference array. We do not use extra space proportional to input bookings beyond this constant-size auxiliary structure (excluding output).

Solution

def corpFlightBookings(bookings: list[list[int]], n: int) -> list[int]:
    # Initialize difference array with size n + 2 to handle boundary conditions easily.
    # Index i corresponds to flight i+1. 
    # We need index 'last' for subtraction, so if last=n (flight), we access index n.
    diff = [0] * (n + 2)

    # Apply difference array updates: O(K) where K is len(bookings)
    for first, last, seats in bookings:
        diff[first - 1] += seats      # Add to start of range
        diff[last] -= seats           # Subtract after end of range (inclusive logic handled by index offset)

    result = []
    current_seats = 0
    
    # Compute prefix sums and build the final answer array: O(N)
    for i in range(n):
        current_seats += diff[i]
        result.append(current_seats)
        
    return result

Edge Cases Handled

  • Full Range Booking: A booking covering [1, n] increments index