LC: 370. Range Addition
https://leetcode.com/problems/range-addition/
You are given an integer length and an array updates where updates[i] = [startIdxi, endIdxi, inci].
You have an array arr of length length with all zeros, and you have some operation to apply on arr. In the ith operation, you should increment all the elements arr[startIdxi], arr[startIdxi + 1], ..., arr[endIdxi] by inci.
Return arr after applying all the updates.
Example 1:
Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
Output: [-2,0,3,5,3]Example 2:
Input: length = 10, updates = [[2,4,6],[5,6,8],[1,9,-4]]
Output: [0,-4,2,2,2,4,4,-4,-4,-4]Constraints:
1 <= length <= 1050 <= updates.length <= 1040 <= startIdxi <= endIdxi < length-1000 <= inci <= 1000
The Essence:
Applying changes over an entire range is inefficient. The idea is then to propagate some change beginning from some start point across its range without modifying those values directly.
Details:
The resulting value of the entire array can be calculated at the end. The individual update queries can be linearly preprocessed before this, with the start of the range getting the positive value and the end of the range getting a negative value. The usage of this system is that, when processing the entire array at the end, these individual updates provide which number should be added to the next element in the array. The negative value terminates this process. This is like a ripple-effect.
This problem can also be solved using Segment Trees. This data structure is important for handling query problems, it's however not the best choice here. Slower both to implement and use.
Solution:
Code can be found here.
Default Code:
Last updated