@@ -0,0 +1,2259 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0A/**%0A * Assume you have an array of length n initialized with all 0's and are given k update operations.%0A * %3Cp%3E%0A * Each operation is represented as a triplet: %5BstartIndex, endIndex, inc%5D which increments each element of subarray%0A * A%5BstartIndex ... endIndex%5D (startIndex and endIndex inclusive) with inc.%0A * %3Cp%3E%0A * Return the modified array after all k operations were executed.%0A * %3Cp%3E%0A * Example:%0A * %3Cp%3E%0A * Given:%0A * %3Cp%3E%0A * length = 5,%0A * updates = %5B%0A * %5B1,  3,  2%5D,%0A * %5B2,  4,  3%5D,%0A * %5B0,  2, -2%5D%0A * %5D%0A * %3Cp%3E%0A * Output:%0A * %3Cp%3E%0A * %5B-2, 0, 3, 5, 3%5D%0A * Explanation:%0A * %3Cp%3E%0A * Initial state:%0A * %5B 0, 0, 0, 0, 0 %5D%0A * %3Cp%3E%0A * After applying operation %5B1, 3, 2%5D:%0A * %5B 0, 2, 2, 2, 0 %5D%0A * %3Cp%3E%0A * After applying operation %5B2, 4, 3%5D:%0A * %5B 0, 2, 5, 5, 3 %5D%0A * %3Cp%3E%0A * After applying operation %5B0, 2, -2%5D:%0A * %5B-2, 0, 3, 5, 3 %5D%0A * %3Cp%3E%0A * Hint:%0A * %3Cp%3E%0A * Thinking of using advanced data structures? You are thinking it too complicated.%0A * For each update operation, do you really need to update all elements between i and j?%0A * Update only the first and end element is sufficient.%0A * The optimal time complexity is O(k + n) and uses O(1) extra space.%0A * %3Cp%3E%0A * Company Tags: Google%0A * Tags: Array%0A */%0Apublic class RangeAddition %7B%0A%0A    /**%0A     * Instead of update all values in the range, we update the start index with the value.%0A     * And the index after end index with negative value. (Safely ignore the last index here.)%0A     * After all updates, the value of current index will be the sum of all values from start to current index.%0A     * %3Cp%3E%0A     * Why?%0A     * During the sum, each value will be added to the position.%0A     * By setting the negative value, it removes the value from the indices after.%0A     */%0A    public int%5B%5D getModifiedArray(int length, int%5B%5D%5B%5D updates) %7B%0A        int%5B%5D res = new int%5Blength%5D;%0A        for (int%5B%5D u : updates) %7B%0A            int start = u%5B0%5D;%0A            int end = u%5B1%5D;%0A            int val = u%5B2%5D;%0A%0A            res%5Bstart%5D += val;%0A            if (end + 1 %3C length) %7B%0A                res%5Bend + 1%5D -= val;%0A            %7D%0A        %7D%0A        int sum = 0;%0A        for (int i = 0; i %3C length; i++) %7B%0A            sum += res%5Bi%5D;%0A            res%5Bi%5D = sum;%0A        %7D%0A        return res;%0A    %7D%0A%0A%7D%0A

add 370 Range Addition