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 ]

Credits:
Special thanks to @vinod23 for adding this problem and creating all test cases.

Solution

Brute-force, O(mn), S(1), (TLE)

m: updates.length
n: length

class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        if (length < 1 || updates == null) {
            return new int[0];
        }
        
        int[] nums = new int[length];
        for (int[] update : updates) {
            for (int i = update[0]; i <= update[1]; ++i) {
                nums[i] += update[2];
            }
        }
        
        return nums;
    }
}

Math, O(m + n), S(1)

很妙的一道题，其实对于每个update[]来说，不必将对应的区间所有值都做increase，只需要将区间的头尾做标记，头 + val，尾 - val。这样最后只需要遍历一次nums[]，记录累加和sum更新nums[i]，就可以了。

class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        if (length < 1 || updates == null) {
            return new int[0];
        }
        
        int[] nums = new int[length];
        for (int[] update : updates) {
            int start = update[0];
            int end = update[1] + 1;
            int val = update[2];
            
            nums[start] += val;
            if (end < nums.length) {
                nums[end] -= val;
            }
        }
        
        int sum = 0;
        for (int i = 0; i < nums.length; ++i) {
            sum += nums[i];
            nums[i] = sum;
        }
        
        return nums;
    }
}