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;
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/range-addition/
    // Time: O(N + U)
    // Space: O(1)
    class Solution {
    public:
        vector<int> getModifiedArray(int length, vector<vector<int>>& A) {
            vector<int> ans(length);
            for (auto &v : A) {
                int start = v[0], end = v[1], diff = v[2];
                ans[start] += diff;
                if (end + 1 < length) ans[end + 1] -= diff;
            }
            int sum = 0;
            for (auto &n : ans) n = sum += n;
            return ans;
        }
    };
    
  • class Solution(object):
      def getModifiedArray(self, length, updates):
        """
        :type length: int
        :type updates: List[List[int]]
        :rtype: List[int]
        """
        ans = [0] * length
        for update in updates:
          start, end, delta = update
          ans[start] += delta
          if end + 1 < length:
            ans[end + 1] -= delta
    
        delta = 0
        for i in range(0, length):
          delta += ans[i]
          ans[i] = delta
        return ans
    
    

All Problems

All Solutions