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:

Input: 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]

Rust Solution

struct Solution;

impl Solution {
    fn get_modified_array(length: i32, updates: Vec<Vec<i32>>) -> Vec<i32> {
        let n = length as usize;
        let mut res = vec![0; n];
        let mut batched = vec![0; n + 1];
        for update in updates {
            let start = update[0] as usize;
            let end = update[1] as usize + 1;
            let inc = update[2];
            batched[start] += inc;
            batched[end] -= inc;
        }
        let mut sum = 0;
        for i in 0..n {
            sum += batched[i];
            res[i] = sum;
        }
        res
    }
}

#[test]
fn test() {
    let length = 5;
    let updates = vec_vec_i32![[1, 3, 2], [2, 4, 3], [0, 2, -2]];
    let res = vec![-2, 0, 3, 5, 3];
    assert_eq!(Solution::get_modified_array(length, updates), res);
}

Having problems with this solution? Click here to submit an issue on github.