You are given an integer length and array updates where updates[i] = [startIdxi, endIdxi, inci]. You have an array “arr” of 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.
https://leetcode.com/problems/range-addition/description/
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
class Solution { //marking the boundary of the update //aux: [0, 0, 0, 0, 0, 0] (length + 1) //update [1, 3, 2] -> [ 0, 2, 0, 0, -2, 0] //update [2, 4, 3] -> [ 0, 2, 3, 0, -2, -3] //update [0, 2, -2] -> [-2, 2, 3, 2, -2, -3] //prefix sum: [-2, 0, 3, 5, 3, 0] //res: [-2, 0, 3, 5, 3] public int[] getModifiedArray(int length, int[][] updates) { //notice the length of the auxiliary array int[] aux = new int[length+1]; //store the effect of the update in startIndex and endIndex+1 position for(int i=0; i<updates.length; i++){ int startIndex = updates[i][0]; int endIndex = updates[i][1]; int val = updates[i][2]; //since there could be overlapping update aux[startIndex] = val + aux[startIndex]; aux[endIndex+1] = -val + aux[endIndex+1]; } int[] res = new int[length]; res[0] = aux[0]; //calculate prefix sum and store it in the resultant array for(int i = 1;i<aux.length-1;i++){ res[i] = aux[i] + res[i-1]; } return res; } } |