LeetCode 370. Range Addition

Question

You are given an integer length and an array updates where updates[i] = [startIdxi, endIdxi, inci].

You have an array arr of length length with all zeros, and you have some operation to apply on arr. In the ith operation, you should increment all the elements arr[startIdxi], arr[startIdxi + 1], ..., arr[endIdxi] by inci.

Return arr after applying all the updates.

Example 1:

Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
Output: [-2,0,3,5,3]

Example 2:

Input: length = 10, updates = [[2,4,6],[5,6,8],[1,9,-4]]
Output: [0,-4,2,2,2,4,4,-4,-4,-4] 

Constraints:

• 1 <= length <= 105
• 0 <= updates.length <= 104
• 0 <= startIdxi <= endIdxi < length
• -1000 <= inci <= 1000

Source: https://leetcode.com/problems/range-addition/

Solution

The idea is like log. We do not directly compute the value of each element, but record the difference of each element’s value relative to its left neighbor. The time complexity is O(n).

public int[] getModifiedArray(int length, int[][] updates) {
    // deltas[i] represents the delta from result[i-1] to result[i]
    // for delta[0], we set result[-1] = 0
    int[] deltas = new int[length];
    for (int[] update: updates) {
        int start = update[0];
        int end = update[1];
        int value = update[2];

        deltas[start] += value;
        if (end + 1 < length) {
            deltas[end + 1] -= value;
        }
    }
    int accumulate = 0;
    int[] result = new int[length];
    for (int i = 0; i < length; i++) {
        accumulate += deltas[i];
        result[i] = accumulate;
    }
    return result;
}