MediumArraysAI interview only
Range Addition
Asked atgoogleamazonmicrosoft
01 · Problem
You start with an array arr of length zeros. You are given a list updates, where updates[i] = [startIdx, endIdx, inc] means: add inc to every element from index startIdx to endIdx, inclusive (indices are 0-based).
Apply all updates and return the final array. If updates is empty, return an array of length zeros.
02 · Examples
Example 01
Input
length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
Output
[-2,0,3,5,3]
After [1,3,2]: [0,2,2,2,0]. After [2,4,3]: [0,2,5,5,3]. After [0,2,-2]: [-2,0,3,5,3].
Example 02
Input
length = 6, updates = [[0,5,1],[2,3,4]]
Output
[1,1,5,5,1,1]
Every element gets 1, then indices 2 and 3 get another 4.
Example 03
Input
length = 3, updates = []
Output
[0,0,0]
No updates are applied, so the array stays all zeros.
03 · Constraints
- 011 <= length <= 105
- 020 <= updates.length <= 104
- 030 <= startIdx <= endIdx < length
- 04-1000 <= inc <= 1000
04 · Optimal complexity
- Time
- O(n + k)
- Space
- O(n)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.