Question
Formatted question description: https://leetcode.ca/all/370.html
370 Range Addition
Assume you have an array of length n initialized with all 0's and are given k update operations.
Each operation is represented as a triplet: [startIndex, endIndex, inc]
which increments each element of subarray A[startIndex ... endIndex] (startIndex and endIndex inclusive) with inc.
Return the modified array after all k operations were executed.
Example:
Given:
length = 5,
updates = [
[1, 3, 2],
[2, 4, 3],
[0, 2, -2]
]
Output:
[-2, 0, 3, 5, 3]
Explanation:
Initial state:
[ 0, 0, 0, 0, 0 ]
After applying operation [1, 3, 2]:
[ 0, 2, 2, 2, 0 ]
After applying operation [2, 4, 3]:
[ 0, 2, 5, 5, 3 ]
After applying operation [0, 2, -2]:
[-2, 0, 3, 5, 3 ]
@tag-array
Algorithm
Suppose our array range is [0, n), the interval to be updated is [start, end], and the updated value is inc.
Then add inc to each number in the interval [start, end], which is equivalent to
- Add inc to all numbers in the interval (start, n)
- Then subtract inc from all the numbers in the interval (end+1, n)
After understanding that this conversion can be done, we still can’t update all the values in the interval every time, so we need to change the marking method.
- The method is to add
inc
to the start position at the beginning of the coordinate, and add-inc
to the position whereend adds 1
.
For example, we need to add 2 to the numbers in the new interval [1, 3], then we add 2 at the position of 1, and subtract 2 at the position of 4, so the array becomes [0, 2, 0, 0, -2]
.
If there is only one operation, how to get the final result?
The answer is to create a cumulative sum array, which becomes [0, 2, 2, 2, 0]
We found that it is exactly equivalent to directly adding 2 to the numbers in the interval [1, 3]. Further analysis, the operation of establishing the accumulation and array actually means that the current number has an effect on the numbers in all subsequent positions.
- Then we add 2 to the start position, which means that every number in the range of [start, n) is added 2
- In fact, only the numbers in the [start, end] interval need to be added by 2
- In order to
eliminate this effect
, we need tosubtract 2 from the numbers in the [end+1, n) interval
, so we subtract 2 from the end+1 position
Then when the accumulation and array is created, it is equivalent to subtracting 2 from all the numbers behind. It should be noted that end may be equal to n-1, then end+1 may be out of range, so we initialize the length of the array to n+1 to avoid the out of range.
Then according to the example in the title, we can get an array, nums = {-2, 2, 3, 2, -2, -3}
, and then add it up and it is the result we require result = {-2, 0 , 3, 5, 3}
Code
Java
import java.util.Arrays;
public class Range_Addition {
public static void main(String[] args) {
Range_Addition out = new Range_Addition();
Solution s = out.new Solution();
System.out.println(Arrays.toString(s.getModifiedArray(5, new int[][]{ {1,3,2}, {2,4,3}, {0,2,-2} })));
}
class Solution {
public int[] getModifiedArray(int length, int[][] updates) {
int[] ans = new int[length];
for (int[] update : updates) {
int start = update[0];
int end = update[1];
int inc = update[2];
ans[start] += inc;
if (end + 1 < length) {
ans[end + 1] += -inc;
}
System.out.println(Arrays.toString(ans));
// [0, 0, 0, 0, 0]
// [0, 2, 0, 0, -2]
// [0, 2, 3, 0, -2]
// [-2, 2, 3, 2, -2]
}
for (int i = 1; i < length; i++) {
ans[i] += ans[i - 1]; // @note
}
// [-2, 0, 3, 5, 3]
return ans;
}
}
}