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.