Get this book -> Problems on Array: For Interviews and Competitive Programming

In this article, we will solve Corporate Flight Bookings problem using prefix sum algorithm. In naive approach, it will take a quadratic O(N^2) time complexity but using a prefix sum approach we can get better time complexity.

**Table of contents**:

- Problem Statement
- Approach 1: Naive method
- Approach 2: Prefix sum approach

## Problem Statement

The Corporate Flight Bookings problem is a problem of finding the total seats reserved for each n flights. we are given i length bookings array which contains a subarray of each first up to last seats of the booking i. The prefix sum approach will do better to solve this 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**

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

we have 5 flight labels.

```
Booking 1 reserved: 10 10(starting from the 1st flight to the 2nd flight)
Booking 2 reserved: 20 20(starting from the 2nd flight to the third flight)
Booking 3 reserved: 25 25 25 25(starting from the 2nd flight to n)
Total seats: 10 55 45 25 25
```

Let us implement using two approaches.

## Approach 1: Naive method

**Algorithm**

- Store the seats value of each flight at an array called answer.
- Iterate through all the values of the bookings.
- for each bookings subarray increment answer by the seats value startig from the first flight to the last flight.

**Explanation:**

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

Note: bookings[i] = [firsti, lasti, seatsi]

Let us create answer array of length *n*

answer = [0,0,0,0,0]

For the first booking, which is [1,2,10] we increment the answer array by 10(seats value) from the the index 0 to 1. our array is zero indexed so we subtract 1 from both the first and last.

answer = [10,10,0,0,0]

For the second, which is [2,3,20] we increment the answer array by 20(seats value) from the index 1 to 2. our array is zero indexed so we subtract 1 from both the first and last.

answer = [10,30,20,0,0]

For the third, which is [2,5,25] we increment the answer array by 20(seats value) from the the index 1 to 4. our array is zero indexed so we subtract 1 from both the first and last.

answer = [10,30,45,25,25]

**Javascript implementation**

```
var corpFlightBookings = function(bookings, n) {
let answer = new Array(n).fill(0); // create an array of answer with length of n and with data type of integer(i.e fill all the elements with 0)
for (let i=0; i<bookings.length; i++) { // iterate through the bookings array.
for (let j=bookings[i][0]-1; j<bookings[i][1]; j++) { // iterate through each bookings subarray.
answer[j]+=bookings[i][2]; // update each of the answer elements with seats value
}
}
return answer;
};
```

**Time and Space complexity**

The time complexity: O(N^2)

The space complexity: O(N)

## Approach 2: Prefix sum approach

**Algorithm**

- create answer array
- Increment answer at index =
*booking[i]*first - 1 by bookings[i] seats - Decrement answer at index =
*booking[i]*last by bookings[i] seats - perform prefix sum array on answer

**Explanation**

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

Note: *bookings[i] = [firsti, lasti, seatsi]*

create an array

*answer = [0,0,0,0,0]*

when **i = 0**

Increment answer at index = booking[0] first - 1 by bookings[0] seats

index = 1 - 1 = 0;

answer = [10,0,0,0,0]

Decrement answer at index = booking[0] last by bookings[0] seats

index = 2

answer = [10,0,-10,0,0]

when **i = 1**

Increment answer at index = booking[1] first - 1 by bookings[1] seats

index = 2 - 1 = 1;

answer = [10,20,0,0,0]

Decrement answer at index = booking[1] last by bookings[1] seats

index = 3

answer = [10,20,-10,-20,0]

when **i = 2**

Increment answer at index = booking[2] first - 1 by bookings[2] seats

index = 2 - 1 = 1;

answer = [10,45,-10,-20,0]

Decrement answer at index = booking[2] last by bookings[2] seats

index = 5 = n leave as it is

answer = [10,45,-10,-20,0]

**Performing prefix sum:**

prefix sum array is the element at index i is the sum of the current element(i) and the previous element(i-1) which is the sum of all elements before it.

answer = [10,45,-10,-20,0] -> [10,55,-10,-20,0]

[10,55,-10,-20,0] -> [10,55,45,-20,0]

[10,55,45,-20,0] -> [10,55,45,25,0]

[10,55,45,25,0] -> [10,55,45,25,25]

answer = [10,55,45,25,25]

**Javascript implementation**

```
var corpFlightBookings = function(bookings, n) {
let answer = new Array(n).fill(0); // create an array of answer with length of n and with data type of integer(i.e fill all the elements with 0)
for (let i=0; i<bookings.length; i++) { // iterate through the bookings array
answer[bookings[i][0]-1] += bookings[i][2]; // increment answer element at index *firsti - 1* with its seats value.
if (bookings[i][1] < n) {
answer[bookings[i][1]] -= bookings[i][2]; // decrement answer element at index *lasti* only if *lasti* is less than *n*
}
}
//prfix sum
for (let i=1; i<n; i++) {
answer[i]+=answer[i-1]; // update *answer i* with the sum of the *answer i* and previous answer(*answeri - 1*)
}
return answer;
};
```

**Time and Space Complexity**

Time Complexity *O(N+M)*, *O(N)* is for the first loop and *O(M)* is the second loop which is used to implement the prefix sum.

Space complexity *O(N)*

With this article at OpenGenus, you must have the complete idea of solving this problem of Corporate Flight Bookings.