308. Range Addition
You manage an array arr of length cells, all starting at 0. You then receive a batch of updates, each a triple [start, end, inc] meaning: add inc to every cell from index start through index end, both endpoints included.
Your function receives the integer length and the list updates; it returns the array after all updates have been applied.
Applying each update cell-by-cell is easy — can you handle the whole batch touching each cell only once at the end?
Example 1:
Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
Output: [-2, 0, 3, 5, 3]
Explanation: Start from [0,0,0,0,0]. Adding 2 on [1,3] gives [0,2,2,2,0]; adding 3 on [2,4] gives [0,2,5,5,3]; adding -2 on [0,2] gives [-2,0,3,5,3].
Example 2:
Input: length = 4, updates = [[0,1,5],[3,3,-1]]
Output: [5, 5, 0, -1]
Explanation: Adding 5 on [0,1] gives [5,5,0,0]; adding -1 on the single cell [3,3] gives [5,5,0,-1]. Index 2 is never touched.
Constraints:
- 1 ≤ length ≤ 10⁵
- 1 ≤ updates.length ≤ 10⁴
- 0 ≤ start ≤ end < length
- -1000 ≤ inc ≤ 1000
Hints:
The direct simulation — loop over every index of every update — is O(length × updates). It works, but every update pays for its full width.
Nobody reads the array until all updates are done. Instead of applying an update, could you just record where it starts and where it stops mattering?
Keep a difference array: diff[start] += inc and diff[end + 1] -= inc. A single prefix-sum pass at the end turns those markers into the final values.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
Expected output: [-2, 0, 3, 5, 3]