[LintCode] Problem 903 - Range Addition

Posted on | In ,

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
2
3
4
5
[
[1,  3,  2],
[2,  4,  3],
[0,  2, -2]
]

return [-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 ]

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int[] getModifiedArray(int length, int[][] updates) {
    int[] array = new int[length + 1];
    int[] sum = new int[length];

    for (int[] update : updates) {
        array[update[0]] += update[2];
        array[update[1] + 1] -= update[2];
    }

    for (int i = 0; i < sum.length; i++)
        sum[i] = (i == 0 ? 0 : sum[i - 1]) + array[i];
    
    return sum;
}