Difference Array

Problem Statement

There are n flights labelled 1 … n. Given a list of bookings where each booking [first, last, seats] reserves seats seats on every flight in [first, last], return an array answer[i] = total seats reserved on flight i.

Input

• bookings — list of [first, last, seats] triples (1-indexed inclusive range).
• n — total number of flights.

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

Output

An array of length n where answer[i] = total seats reserved on flight i + 1.

[10, 55, 45, 25, 25]

Constraints

• 1 ≤ n ≤ 2·10⁴
• 1 ≤ bookings.length ≤ 2·10⁴
• 1 ≤ firstᵢ ≤ lastᵢ ≤ n
• 1 ≤ seatsᵢ ≤ 10⁴

Intuition

Naïvely adding seats to every index in [first, last] is O(range) per booking. A difference array converts each update into exactly two O(1) writes: diff[l] += v and diff[r+1] -= v. Prefix-summing the difference array reconstructs the actual values.

diff = [0, 0, 0, 0, 0, 0]
 
After [1,2,10]:  [+10,   0, −10,   0,   0,   0]
After [2,3,20]:  [+10, +20, −10, −20,   0,   0]
After [2,5,25]:  [+10, +45, −10, −20,   0, −25]
 
Prefix sum:      [ 10,  55,  45,  25,  25]
                   ↑                    ↑
                  flight 1          flight 5

Solution

def corpFlightBookings(bookings: list[list[int]], n: int) -> list[int]:
    diff = [0] * (n + 1)
    for first, last, seats in bookings:
        diff[first - 1] += seats
        diff[last] -= seats
 
    result, running = [], 0
    for i in range(n):
        running += diff[i]
        result.append(running)
 
    return result

function corpFlightBookings(bookings: number[][], n: number): number[] {
    const diff = new Array(n + 1).fill(0);
    for (const [first, last, seats] of bookings) {
        diff[first - 1] += seats;
        diff[last] -= seats;
    }
 
    const result: number[] = [];
    let running = 0;
    for (let i = 0; i < n; i++) {
        running += diff[i];
        result.push(running);
    }
 
    return result;
}

Complexity

Edge Case Thinking