Problem Description

You have n flights numbered from 1 to n.

You're given an array called bookings where each element bookings[i] = [first_i, last_i, seats_i] represents a booking that reserves seats_i seats on every flight from flight number first_i to flight number last_i (inclusive).

Your task is to return an array answer of length n, where answer[i] tells you the total number of seats reserved for flight i.

For example, if you have a booking [1, 3, 10], it means 10 seats are reserved on flights 1, 2, and 3. If another booking is [2, 4, 20], then 20 additional seats are reserved on flights 2, 3, and 4. The final answer would show the cumulative seats reserved for each flight after processing all bookings.

The solution uses a difference array technique. Instead of updating every flight in the range [first, last] individually (which would be inefficient), it marks the start and end of each booking range. It adds seats at position first - 1 (converting to 0-indexed) and subtracts seats at position last (which is one position after the last flight in the range). After processing all bookings this way, a prefix sum calculation using accumulate gives the final seat count for each flight.

Intuition

The naive approach would be to iterate through each booking and add the seats to every flight in the range [first, last]. However, this would take O(m × k) time where m is the number of bookings and k is the average range size, which can be inefficient when ranges are large.

The key insight is recognizing that we're performing the same operation (adding a constant value) to a contiguous range of elements multiple times. This is a classic scenario for the difference array technique.

Think of it like turning lights on and off in a hallway. Instead of walking to each light switch individually, you could just mark where the lit section starts and where it ends. When you walk through the hallway later, you know which lights should be on based on these markers.

Similarly, for each booking range [first, last] with seats seats:

• We mark the beginning of the range by adding seats at position first - 1
• We mark the end of the range by subtracting seats at position last (the position right after the range ends)

Why does this work? When we compute the prefix sum later:

• At position first - 1, the running sum increases by seats
• This increased value carries forward to all subsequent positions
• At position last, the running sum decreases by seats, effectively "turning off" the addition for flights beyond the range

This transforms an O(m × k) problem into an O(m + n) problem, where we only need O(m) operations to process all bookings and O(n) to compute the final prefix sum.

Learn more about Prefix Sum patterns.

Solution Approach

The solution implements the difference array technique to efficiently handle range updates:

Step 1: Initialize the difference array

ans = [0] * n

We create an array of size n initialized with zeros to store our difference values.

Step 2: Process each booking

for first, last, seats in bookings:
    ans[first - 1] += seats
    if last < n:
        ans[last] -= seats

For each booking [first, last, seats]:

• Add seats at index first - 1 (converting from 1-indexed to 0-indexed). This marks the start of the range where seats are added.
• Subtract seats at index last (which is last + 1 in 1-indexed terms, but just last in 0-indexed). This marks where the seat addition should stop.
• The condition if last < n ensures we don't go out of bounds when the booking extends to the last flight.

Step 3: Calculate prefix sum

return list(accumulate(ans))

The accumulate function computes the running sum of the difference array. Each position i in the result contains the sum of all values from index 0 to i in the difference array.

Why this works: When we compute the prefix sum:

• At any index i, the value represents the cumulative effect of all "start" markers before or at i minus all "end" markers before i
• This automatically gives us the total seats reserved for flight i + 1

Time Complexity: O(m + n) where m is the number of bookings and n is the number of flights Space Complexity: O(n) for the answer array

Example Walkthrough

Let's walk through a small example with n = 5 flights and the following bookings:

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

Step 1: Initialize difference array

ans = [0, 0, 0, 0, 0]

Step 2: Process each booking

Booking 1: [1, 3, 10] - Reserve 10 seats on flights 1-3

• Add 10 at index 0 (flight 1, converted to 0-indexed)
• Subtract 10 at index 3 (one position after flight 3)

ans = [10, 0, 0, -10, 0]

Booking 2: [2, 4, 20] - Reserve 20 seats on flights 2-4

• Add 20 at index 1 (flight 2, converted to 0-indexed)
• Subtract 20 at index 4 (one position after flight 4)

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

Booking 3: [2, 5, 25] - Reserve 25 seats on flights 2-5

• Add 25 at index 1 (flight 2, converted to 0-indexed)
• Since last = 5 equals n, we skip the subtraction (no flights after 5)

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

Step 3: Calculate prefix sum Computing the running sum:

• Index 0: 10
• Index 1: 10 + 45 = 55
• Index 2: 55 + 0 = 55
• Index 3: 55 + (-10) = 45
• Index 4: 45 + (-20) = 25

Final Result:

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

This means:

• Flight 1: 10 seats reserved (from booking 1)
• Flight 2: 55 seats reserved (10 from booking 1 + 20 from booking 2 + 25 from booking 3)
• Flight 3: 55 seats reserved (10 from booking 1 + 20 from booking 2 + 25 from booking 3)
• Flight 4: 45 seats reserved (20 from booking 2 + 25 from booking 3)
• Flight 5: 25 seats reserved (only from booking 3)

The difference array technique efficiently handles all range updates in O(m) time and computes the final answer in O(n) time, avoiding the need to update each flight individually for every booking.

Solution Implementation

Time and Space Complexity

The time complexity is O(m + n), where m is the number of bookings and n is the number of flights. The algorithm iterates through all m bookings once to update the difference array, which takes O(m) time. Then, it uses accumulate to compute the prefix sum over n elements, which takes O(n) time. Therefore, the total time complexity is O(m + n).

The space complexity is O(1) if we ignore the space consumption of the answer array. The algorithm only uses the answer array ans to store the result, which is required for the output. No additional auxiliary space proportional to the input size is used beyond this required output array.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Index Confusion Between 1-indexed and 0-indexed

The most common mistake is mishandling the conversion between 1-indexed flight numbers (given in the problem) and 0-indexed array positions (used in implementation).

Pitfall Example:

# WRONG: Forgetting to convert to 0-indexed
difference_array[first_flight] += seats_to_add  # Should be first_flight - 1

# WRONG: Incorrect end boundary
difference_array[last_flight - 1] -= seats_to_add  # Should be last_flight, not last_flight - 1

Correct Approach:

• Start of range: Use first_flight - 1 (converts 1-indexed to 0-indexed)
• End of range: Use last_flight (this is already the position AFTER the last flight in 0-indexed terms)

2. Boundary Check Omission

Forgetting to check if last_flight < n before subtracting seats can cause an index out of bounds error.

Pitfall Example:

# WRONG: No boundary check
difference_array[last_flight] -= seats_to_add  # Crashes when last_flight == n

Correct Approach:

if last_flight < n:
    difference_array[last_flight] -= seats_to_add

3. Manual Prefix Sum Implementation Errors

If implementing prefix sum manually instead of using accumulate, off-by-one errors are common.

Pitfall Example:

# WRONG: Starting from index 1 instead of 0
for i in range(1, n):
    difference_array[i] += difference_array[i - 1]

# This misses accumulating the first element properly

Correct Manual Implementation:

# Option 1: Modify in-place starting from index 1
for i in range(1, n):
    difference_array[i] += difference_array[i - 1]
return difference_array

# Option 2: Use a separate result array
result = [difference_array[0]]
for i in range(1, n):
    result.append(result[-1] + difference_array[i])
return result

4. Understanding the Difference Array Logic

A conceptual pitfall is thinking you need to subtract at last_flight - 1 or add at first_flight without the -1 adjustment.

Key Insight:

• We add seats at the START of the range (index first - 1 in 0-indexed)
• We subtract seats AFTER the range ends (index last in 0-indexed, which represents position last + 1 in 1-indexed terms)
• This ensures the prefix sum includes the seats for all flights from first to last inclusive