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.

Train of Thought

[i,j] 的变化就是一个区间, 只要i变了, 后面的都跟着变, 但是要到j结束 给一个[start, end, val] 设立一个start标记, 表示从它开始的都加上当前的val, 但是如何结束呢, 在end + 1位置设立一个-val, 这样就消除了start的影响. 最后再遍历一遍数组, 求和就可以得到全部变化的结果

Code

public class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        //brute force
        // int[] res = new int[length];

        // for (int i = 0; i < updates.length;) {
        //     int m = updates[i][0], n = updates[i][1], val = updates[i][2];
        //     for (int j = m; j <= n; j++) {
        //         res[j] += val;
        //     }
        // }

        // return res;

        int[] res = new int[length];

        for (int i = 0; i < updates.length; i++) {
            int start = updates[i][0], end = updates[i][1], val = updates[i][2];
            res[start] += val;
            if (end < length - 1) {
                res[end + 1] -= val;
            }
        }

        int sum = 0;
        for (int i = 0; i < length; i++) {
            sum += res[i];
            res[i] = sum;
        }

        return res;
    }
}

Complexity