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 where end 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 to subtract 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;
        }
    }
}

All Problems

All Solutions