Range Addition
Core idea: A "+inc to every index in
[start, end]" update is really just two point edits on a difference array —+incwhere the range opens,-incwhere it closes. Record allkupdates as point edits inO(1)each, then one prefix sum sweeps left to right and reconstitutes the whole array inO(n).
Problem, rephrased
Imagine you run a stadium box office. You have 1,000 seats, numbered 0 .. 999, and a stack of group bookings. Each booking says "seats 100 through 250, add 1 person each" or "seats 50 through 999, add 4 people each." After processing the whole stack you need the occupancy of every single seat.
The lazy instinct is: for each booking, walk every seat in its range and bump the counter. With a tall stack of bookings over a wide seat map, that walking dominates everything.
Formally (LeetCode 370): you're given a length-n array initialized to all zeros and a list of k updates. Each update is a triple (start, end, inc) and means add inc to every index i with start <= i <= end (both ends inclusive). After applying all updates in order, return the final array.
| n | updates | Output | Why |
|---|---|---|---|
| 5 | [[1,3,2],[2,4,3],[0,2,-2]] |
[-2,0,3,5,3] |
sum the three overlapping bumps per index |
| 4 | [[0,3,4]] |
[4,4,4,4] |
one update covering the whole array |
| 3 | [[1,1,5]] |
[0,5,0] |
a single-index range (start == end) |
| 4 | [] |
[0,0,0,0] |
no updates → all zeros |
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson