Corporate Flight Bookings solution and explanation
Google
9 more videos on this problem
Corporate Flight Bookings | Leetcode 1109 | Line Sweep Technique Concepts & Questions - 10 | MIKcodestorywithMIK · 16:09 · 2K views
1109. Corporate Flight Bookings (LeetCode Weekly Contest 144)Kelvin Chandra · 4:15 · 2K views
1109. Corporate Flight Bookings (Leetcode Medium)Programming Live with Larry · 15:22 · 2K views
Leetcode 1109. Corporate Flight Bookings | SWEEP LINE | PREFIX SUMCodingVerse · 13:29 · 1K views
Leetcode 1109. Corporate Flight Bookings (difference array)LetsCode · 7:06 · 1K views
LeetCode in JavaScript - Corporate Flight BookingsSayantan Codes · 13:00 · 988 views
leetcode 1109 corporate flight bookingsDzung T Dang · 20:52 · 729 views
米开：LeetCode 1109. Corporate Flight BookingsM.C米开朗基罗 · 6:49 · 655 views
LeetCode 1109 | Corporate Flight Bookings | Array | JavaSleepy Cracker · 2:07 · 603 views
【每日一题】1109. Corporate Flight Bookings, 5/23/2021Huifeng Guan · 12:44 · 494 views
The problem
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 * 1041 <= bookings.length <= 2 * 104bookings[i].length == 31 <= firsti <= lasti <= n1 <= 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.
from typing import List
def corpFlightBookings(bookings: List[List[int]], n: int) -> List[int]:
result = [0] * n
for first, last, seats in bookings:
for i in range(first - 1, last):
result[i] += seats
return resultimport java.util.*;
public class Solution {
public int[] corpFlightBookings(int[][] bookings, int n) {
int[] result = new int[n];
for (int[] booking : bookings) {
for (int i = booking[0] - 1; i < booking[1]; i++) {
result[i] += booking[2];
}
}
return result;
}
}#include <vector>
std::vector<int> corpFlightBookings(std::vector<std::vector<int>>& bookings, int n) {
std::vector<int> result(n, 0);
for(auto& booking : bookings) {
for(int i = booking[0] - 1; i < booking[1]; i++) {
result[i] += booking[2];
}
}
return result;
}var corpFlightBookings = function(bookings, n) {
let result = new Array(n).fill(0);
bookings.forEach(([first, last, seats]) => {
for (let i = first - 1; i < last; i++) {
result[i] += seats;
}
});
return result;
};#include <stdlib.h>
int* corpFlightBookings(int** bookings, int bookingsSize, int* bookingsColSize, int n, int* returnSize) {
int* answer = (int*)calloc(n, sizeof(int));
for(int i = 0; i < bookingsSize; i++) {
for(int j = bookings[i][0] - 1; j <= bookings[i][1] - 1; j++) {
answer[j] += bookings[i][2];
}
}
*returnSize = n;
return answer;
}public class Solution {
public int[] CorpFlightBookings(int[][] bookings, int n) {
int[] result = new int[n];
foreach (var booking in bookings) {
for (int i = booking[0] - 1; i < booking[1]; i++) {
result[i] += booking[2];
}
}
return result;
}
}This Python solution initializes a result list with zeros. It iterates over each booking and uses a nested loop to increment each element in the result list by the number of seats for the flights specified in the booking range.
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: 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.
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
if last < n:
diff[last] -= seats
result = [0] * n
result[0] = diff[0]
for i in range(1, n):
result[i] = result[i - 1] + diff[i]
return resultimport java.util.*;
public class Solution {
public int[] corpFlightBookings(int[][] bookings, int n) {
int[] diff = new int[n + 1];
for (int[] booking : bookings) {
diff[booking[0] - 1] += booking[2];
if (booking[1] < n) diff[booking[1]] -= booking[2];
}
int[] result = new int[n];
result[0] = diff[0];
for (int i = 1; i < n; i++) {
result[i] = result[i - 1] + diff[i];
}
return result;
}
}#include <vector>
std::vector<int> corpFlightBookings(std::vector<std::vector<int>>& bookings, int n) {
std::vector<int> diff(n + 1, 0);
for(auto& booking : bookings) {
diff[booking[0] - 1] += booking[2];
if (booking[1] < n) diff[booking[1]] -= booking[2];
}
std::vector<int> result(n, 0);
result[0] = diff[0];
for (int i = 1; i < n; i++) {
result[i] = result[i - 1] + diff[i];
}
return result;
}var corpFlightBookings = function(bookings, n) {
let diff = new Array(n + 1).fill(0);
bookings.forEach(([first, last, seats]) => {
diff[first - 1] += seats;
if (last < n) diff[last] -= seats;
});
let result = new Array(n).fill(0);
result[0] = diff[0];
for (let i = 1; i < n; i++) {
result[i] = result[i - 1] + diff[i];
}
return result;
};#include <stdlib.h>
int* corpFlightBookings(int** bookings, int bookingsSize, int* bookingsColSize, int n, int* returnSize) {
int* diff = (int*)calloc(n + 1, sizeof(int));
for (int i = 0; i < bookingsSize; i++) {
diff[bookings[i][0] - 1] += bookings[i][2];
if (bookings[i][1] < n) diff[bookings[i][1]] -= bookings[i][2];
}
int* result = (int*)calloc(n, sizeof(int));
result[0] = diff[0];
for (int i = 1; i < n; i++) {
result[i] = result[i - 1] + diff[i];
}
*returnSize = n;
return result;
}public class Solution {
public int[] CorpFlightBookings(int[][] bookings, int n) {
int[] diff = new int[n + 1];
foreach (var booking in bookings) {
diff[booking[0] - 1] += booking[2];
if (booking[1] < n) diff[booking[1]] -= booking[2];
}
int[] result = new int[n];
result[0] = diff[0];
for (int i = 1; i < n; i++) {
result[i] = result[i - 1] + diff[i];
}
return result;
}
}This Python solution applies the difference array method, where each booking updates the bounds of the difference array. We then apply a prefix sum to convert the difference result into the final seats reservation results.
Time Complexity: O(n + m) where n is the number of flights and m is the number of bookings.
Space Complexity: O(n) due to the arrays used.
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).
func corpFlightBookings(bookings [][]int, n int) []int {
ans := make([]int, n)
for _, e := range bookings {
first, last, seats := e[0], e[1], e[2]
ans[first-1] += seats
if last < n {
ans[last] -= seats
}
}
for i := 1; i < n; i++ {
ans[i] += ans[i-1]
}
return ans
}impl Solution {
#[allow(dead_code)]
pub fn corp_flight_bookings(bookings: Vec<Vec<i32>>, n: i32) -> Vec<i32> {
let mut ans = vec![0; n as usize];
// Build the difference vector first
for b in &bookings {
let (l, r) = ((b[0] as usize) - 1, (b[1] as usize) - 1);
ans[l] += b[2];
if r < (n as usize) - 1 {
ans[r + 1] -= b[2];
}
}
// Build the prefix sum vector based on the difference vector
for i in 1..n as usize {
ans[i] += ans[i - 1];
}
ans
}
}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:
- Single Point Update
update(x, delta): Add a value delta to the number at position x in the sequence; - 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).
type BinaryIndexedTree struct {
n int
c []int
}
func newBinaryIndexedTree(n int) *BinaryIndexedTree {
c := make([]int, n+1)
return &BinaryIndexedTree{n, c}
}
func (this *BinaryIndexedTree) update(x, delta int) {
for x <= this.n {
this.c[x] += delta
x += x & -x
}
}
func (this *BinaryIndexedTree) query(x int) int {
s := 0
for x > 0 {
s += this.c[x]
x -= x & -x
}
return s
}
func corpFlightBookings(bookings [][]int, n int) []int {
tree := newBinaryIndexedTree(n)
for _, e := range bookings {
first, last, seats := e[0], e[1], e[2]
tree.update(first, seats)
tree.update(last+1, -seats)
}
ans := make([]int, n)
for i := range ans {
ans[i] = tree.query(i + 1)
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Direct Array Manipulation | Time Complexity: O(n * m) where n is the number of flights and m is the number of bookings. |
| Approach 2: Difference Array Technique | Time Complexity: O(n + m) where n is the number of flights and m is the number of bookings. |
| Difference Array | – |
| Binary Indexed Tree + Difference Idea | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Array Manipulation | O(m * n) | O(n) | Small inputs or when implementing a straightforward range update without optimization |
| Difference Array Technique | O(n + m) | O(n) | Large booking ranges or many updates where efficient range processing is required |
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.