99. Batch Range Updates
A warehouse has n shelves numbered 0 to n - 1, all starting with a stock level of 0. Workers submit a batch of adjustments in updates, where each entry is [a, b, v]: add v units (possibly negative) to every shelf between positions a and b, inclusive. The two endpoints may be given in either order, so the affected shelves run from min(a, b) to max(a, b).
Apply every adjustment and return an array of length n with the final stock level of each shelf. The list may be empty, in which case every level stays 0.
Example 1
- Input:
- n = 5, updates = [[1,3,2],[0,1,5]]
- Output:
- [5,7,2,2,0]
- Explanation:
Shelves 1 to 3 gain 2 and shelves 0 to 1 gain 5, giving [5, 7, 2, 2, 0].
Example 2
- Input:
- n = 4, updates = [[3,1,-2],[2,2,4]]
- Output:
- [0,-2,2,-2]
- Explanation:
The first update covers shelves 1 to 3 (endpoints reversed) with -2 and the second adds 4 to shelf 2, giving [0, -2, 2, -2].
Constraints
- 1 ≤ n ≤ 100000
- 0 ≤ updates.length ≤ 100000
- updates[i].length == 3
- 0 ≤ updates[i][0], updates[i][1] < n
- -1000 ≤ updates[i][2] ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n + m)
- Space
- O(n)