Corporate Flight Bookings
Medium Difference array
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
There are n flights. Each booking [first, last, seats] reserves seats on every flight from first to last. Return the total seats for each flight.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: many bookings each add seats to a range of flights; total per flight?
Why this works: instead of updating every flight in a range, mark +seats where the range starts and -seats just after it ends. One running sum at the end spreads the marks.
Example: bookings [1,2,10], [2,3,20], [2,5,25], n = 5
marks: +10 at 1, -10 at 3; +20 at 2, -20 at 4; +25 at 2running: 10, 55, 45, 25, 25
✦Hints open one at a time
↗Approach
Difference array: diff[first-1] += seats and diff[last] -= seats (if in range). Then take the running sum. Each booking costs O(1).
</>Solution (Java)
class Solution {
public int[] corpFlightBookings(int[][] bookings, int n) {
int[] ans = new int[n];
for (int[] b : bookings) {
ans[b[0] - 1] += b[2]; // range starts
if (b[1] < n) ans[b[1]] -= b[2]; // range ends after flight b[1]
}
for (int i = 1; i < n; i++) ans[i] += ans[i - 1];
return ans;
}
}!Common mistake
Mixing 1-based flight numbers with 0-based indexes — subtract one from first, and last becomes the "after" index.
- Time: O(n + b), b = number of bookings.
- Space: O(n).
