Leetcode #370. Range Addition

[yokostan]

Brute Force, beats 27%:

 class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        int[] res = new int[length];
        if (updates == null || updates.length == 0 || updates[0].length == 0) return res;
        int n = updates.length;

        for (int i = 0; i < n; i++) {
            helper(res, updates[i][0], updates[i][1], updates[i][2]);
        }

        return res;
    }

    public void helper(int[] res, int start, int end, int inc) {
        for (int i = start; i <= end; i++) {
            res[i] += inc;
        }
    }
}

class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        int[] res = new int[length];
        if (updates == null || updates.length == 0 || updates[0].length == 0) return res;
        int n = updates.length;

        for (int i = 0; i < n; i++) {
            int start = updates[i][0];
            int end = updates[i][1];
            int value = updates[i][2];
            res[start] += value;

            if (end < length - 1) {
                res[end + 1] -= value;
            }
        }

        int sum = 0;
        for (int i = 0; i < length; i++) {
            sum += res[i];
            res[i] = sum;
        }

        return res;
    }
}

[yokostan]

Just store every start index for each value and at end index plus one minus it

for example it will look like:

[1 , 3 , 2] , [2, 3, 3] (length = 5)

res[ 0, 2, ,0, 0 -2 ]

res[ 0 ,2, 3, 0, -5]

sum 0, 2, 5, 5, 0

res[0, 2, 5, 5, 0]