Prefix Sum — Corporate Flight Bookings
↗ LeetCode: Corporate Flight Bookings · Medium · pattern chapter →
Given n flights and bookings [first, last, seats], return an array where index i = total seats booked on flight i+1.
Example 1 — bookings=[[1,2,10],[2,3,20],[2,5,25]], n=5 → [10,55,45,25,25]Example 2 — bookings=[[1,2,10],[2,2,15]], n=2 → [10,25]Example 3 — bookings=[[1,1,5]], n=3 → [5,0,0]
Constraints — 1 ≤ n ≤ 2·10⁴; 1 ≤ bookings.length ≤ 2·10⁴. Brute applies each booking to a range — O(bookings·n) = 10⁵·2·10⁴ = 2·10⁹ ops (TLE). Difference-array + prefix sum is O(bookings + n) = 3·10⁵ ops = <5 ms.
Interview timer00:00
Approach 1 — Direct fill
For each booking, add seats to every index in [first-1, last-1]. O(n · m).
Approach 2 — Difference array (canonical)
Insight. Range-add on many disjoint queries is O(1) per query on a difference array: +seats at first-1, -seats at last. Prefix sum recovers the totals.
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];
}
for (int i = 1; i < n; i++) diff[i] += diff[i - 1];
return Arrays.copyOf(diff, n);
}Complexity — Time O(n + m); Space O(n).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Direct fill | O(n·m) | O(n) | baseline |
| Difference array | O(n+m) | O(n) | optimum |
When to use which
- Many range-add queries, one final read → difference array + one prefix sum.
- Queries interleaved with reads → segment tree with lazy propagation.
- Range assignment (not add) → different structure — sweep line or seg tree.
Related problems
- Car Pooling — identical idea with capacity check
- Range Addition — the primitive
- Range Addition II