2.5 Range Addition

Description

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 ] Hint:

Thinking of using advanced data structures? You are thinking it too complicated. For each update operation, do you really need to update all elements between i and j? Update only the first and end element is sufficient. The optimal time complexity is O(k + n) and uses O(1) extra space. Credits: Special thanks to @vinod23 for adding this problem and creating all test cases.

Method

According to the hint, we know that we just need to updates two values of the start and end, but the problem is how to know it is a end of a interval

so we set the end + 1 to -value recursively, then when we for loop from the start of array, we treat each value as a start of a interval, we accumulate it value one by one, so if this value should end at j, since j + 1 we have a -v, we will decrease the v from the sum, so it doesn't have influence with the elements after this end.

0 0 0 0 0 2 -2 3 -2 -2 2
-2 0 3 5 3

Time and Space Complexity

o(n + k)

Code

public class Solution {

   public int[] getModifiedArray(int length, int[][] updates) {
       int[] res = new int[length];
       if (updates == null || updates.length == 0){
           return res;
       }
       for (int i = 0; i < updates.length; i++){
            int start = updates[i][0];
            int end = updates[i][1];
            int value = updates[i][2];

            res[start] += value;
            if (end < length - 1){
                res[end + 1] -= value;
            }
       }
       int sum = 0;
       for (int i = 0; i < length; i++){
            sum += res[i];
            res[i] = sum;
       }
       return res;
}

}