Skip to main content
Talentd

Corporate Flight Bookings - Solution & Explanation

MediumArrayPrefix Sum21 min readAsked at: Microsoft, Goldman Sachs, Meta +2
Practice this problem

Problem Statement

There are n flights that are labeled from 1 to n.

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

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

 

Example 1:

Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
Output: [10,55,45,25,25]
Explanation:
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]
Explanation:
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

Approach Overview

Problem Overview: You receive booking operations where each entry [first, last, seats] adds seats to every flight from first to last. With n flights and multiple bookings, the goal is to compute the final number of seats reserved for each flight efficiently.

Approach 1: Direct Array Manipulation (Time: O(m * n), Space: O(n))

Create an array of size n to store seat counts for each flight. For every booking, iterate from first to last and add the number of seats to each position in the array. This approach mirrors the booking definition directly: process each range and update every affected flight. While simple to implement, it becomes expensive when bookings span large ranges or when both n and m are large. The repeated range updates make it inefficient compared to prefix-based techniques often used with array problems.

Approach 2: Difference Array Technique (Time: O(n + m), Space: O(n))

Instead of updating every flight inside a booking range, mark only the boundaries. Add seats at index first - 1 and subtract seats at index last (if it exists). This creates a difference array that represents how seat counts change between indices. After processing all bookings, compute a running prefix sum across the array to recover the final seat counts for each flight. This technique converts multiple range updates into constant-time boundary updates and a single linear pass using a prefix sum. The result reduces the complexity dramatically from repeated updates to a single accumulation pass.

Recommended for interviews: Interviewers expect the Difference Array or Prefix Sum approach. The brute force range update demonstrates baseline reasoning, but the boundary-marking trick shows you understand how to optimize repeated range operations in array problems. The optimal solution runs in O(n + m) time and scales cleanly even when bookings cover large flight ranges.

Approach 1: Approach 1: Direct Array Manipulation

This approach involves updating a direct array for each booking. We simply iterate over each booking, updating the flights within the specified range. This approach is straightforward but could be inefficient for large inputs due to repeated updates.

This C solution uses calloc to zero-initialize the answer array of size n. It then loops through each booking, and for each booking, it loops through the range of flights affected by the booking, updating the answer array by adding the booked seats.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * m) where n is the number of flights and m is the number of bookings.
Space Complexity: O(n) for storing the result.

Try this approach in the editor →

Approach 2: Approach 2: Difference Array Technique

To optimize the update operations, we can employ a difference array. By storing the increment at the start of the range and the decrement right after the end of the range, we can later use prefix sums to compute the final result. This reduces the time complexity significantly for processing each booking.

The C solution uses a difference array to store the net effect of each booking. We increment at the start index and decrement right after the end index. Then we compute the prefix sums to get the final result.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + m) where n is the number of flights and m is the number of bookings.
Space Complexity: O(n) for storing the result and additional space used by the difference array.

Try this approach in the editor →

Approach 3: 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.

The time complexity is O(n), where n is the number of flights. Ignoring the space consumption of the answer, the space complexity is O(1).

Code

PythonJavaC++GoRustJavaScript

Python

Java

C++

Go

Rust

JavaScript

Try this approach in the editor →

Approach 4: 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.

The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the number of flights.

Here is a basic introduction to the binary indexed tree:

A binary indexed tree, also known as a "Binary Indexed Tree" or Fenwick tree. It can efficiently implement the following two operations:

  1. Single Point Update update(x, delta): Add a value delta to the number at position x in the sequence;
  2. Prefix Sum Query query(x): Query the interval sum of the sequence [1,...x], that is, the prefix sum of position x.

The time complexity of these two operations is O(log n).

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Direct Array Manipulation

Time Complexity: O(n * m) where n is the number of flights and m is the number of bookings.
Space Complexity: O(n) for storing the result.

Approach 2: Difference Array Technique

Time Complexity: O(n + m) where n is the number of flights and m is the number of bookings.
Space Complexity: O(n) for storing the result and additional space used by the difference array.

Difference Array—
Binary Indexed Tree + Difference Idea—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Array ManipulationO(m * n)O(n)Small inputs or when implementing a straightforward range update without optimization
Difference Array TechniqueO(n + m)O(n)Large booking ranges or many updates where efficient range processing is required

Video Solution

Corporate Flight Bookings | Leetcode 1109 | Line Sweep Technique Concepts & Questions - 10 | MIK • codestorywithMIK • 2,922 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Corporate Flight Bookings easy or hard?
Corporate Flight Bookings is a medium difficulty problem. The challenge comes from recognizing that repeated range updates are inefficient and that a difference array with prefix sums can reduce the complexity significantly.
Corporate Flight Bookings Python/Java solution
Python, Java, C++, and other implementations follow the same logic: initialize an array of size n, apply difference array updates for each booking, then compute the prefix sum to produce final results. The algorithm remains O(n + m) regardless of language.
How to solve Corporate Flight Bookings in O(n)?
Use a difference array to mark seat changes at the start and end of each booking range. Add seats at index first-1 and subtract seats at index last. After processing all bookings, compute a prefix sum across the array to produce the final seat counts for each flight.
What is the best approach for Corporate Flight Bookings?
The best approach uses the Difference Array technique combined with a prefix sum. Instead of updating every flight in a booking range, mark the start and end boundaries and then compute cumulative totals. This reduces the time complexity to O(n + m), where n is the number of flights and m is the number of bookings.
Is Corporate Flight Bookings asked at Google/Amazon/Meta?
Corporate Flight Bookings represents a classic range update problem using prefix sums. Variations of this technique frequently appear in interviews at large tech companies such as Amazon, Google, and Meta because it tests understanding of array manipulation and optimization strategies.
What data structure is used in Corporate Flight Bookings?
The problem primarily uses arrays. The optimized solution relies on a difference array to store boundary updates and a prefix sum pass to compute cumulative seat counts across flights.
What is the time complexity of Corporate Flight Bookings?
The optimal solution runs in O(n + m) time using the difference array and prefix sum technique. Processing bookings takes O(m) because each update modifies only two indices, and computing the final seat counts requires a single O(n) prefix sum pass.

Ready to solve this problem?

Practice Corporate Flight Bookings with our built-in code editor and test cases.

Practice on FleetCode
Previous

Zero Array Transformation II

Next

Zero Array Transformation III