Problem 5.6 · Prefix SumMedium

Corporate Flight Bookings

What it teaches: Apply many range additions in O(1) each with a difference array, then one prefix sum.

Practise it on judges as “Corporate Flight Bookings”.

The problem

There are n flights numbered 1 to n. Each booking [first, last, seats] reserves seats seats on every flight from first to last inclusive. Return an array of length n with the total seats reserved on each flight.

Example 1

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

Constraints

1 ≤ n ≤ 2 × 10⁴
1 ≤ bookings.length ≤ 2 × 10⁴
1 ≤ first ≤ last ≤ n

Pattern clues in the wording

→ Many "add v to a range" updates
→ Only the final totals are needed

These clues point to Difference Array: Apply many "add v to range [l, r]" updates in O(1) each by marking +v at l and -v at r + 1, then take a prefix sum once.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] diff = new int[n + 1];
        int[] out = new int[n];
        return out;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	bookings = [[1,2,10],[2,3,20],[2,5,25]] n = 5	[10,55,45,25,25]
2	bookings = [[1,2,10],[2,2,15]] n = 2	[10,25]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Add to every flight · O(n · b)2. Optimal: difference array · O(n + b)

Add to every flight

Time O(n · b) Space O(n)

For each booking, loop from first to last adding seats.

Approach 1

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] out = new int[n];
        for (int[] b : bookings)
            for (int f = b[0]; f <= b[1]; f++) out[f - 1] += b[2];
        return out;
    }
}

Verdict: 4 × 10⁸ steps in the worst case: too slow.

Optimal: difference array

Time O(n + b) Space O(n)

diff[first − 1] += seats and diff[last] -= seats (0-based, so last is the index after the range). Then a running sum over diff gives each flight's total.

▶ Dry run: Marking range edgesbookings = [[1,2,10], [2,3,20], [2,5,25]], n = 5

-10

Step 1/4[1, 2, 10]: +10 at index 0, −10 at index 2.

Approach 2

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] diff = new int[n + 1];
        for (int[] b : bookings) {
            diff[b[0] - 1] += b[2];
            diff[b[1]] -= b[2];
        }
        int[] out = new int[n];
        int running = 0;
        for (int i = 0; i < n; i++) {
            running += diff[i];
            out[i] = running;
        }
        return out;
    }
}

Verdict: Each booking costs O(1).

Before you submit

Edge cases and common mistakes

Test these inputs

Booking covering all flights
Booking of a single flight
Last flight included (needs diff of length n + 1)

Mistakes people make

Mixing 1-based flight numbers with 0-based indexes.
Allocating diff of length n and writing past the end.

Interview

Follow-up questions

What if you also need totals in the middle of processing bookings?