package com.fishercoder.solutions;

/**
 * 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:

 Given:

 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 ]

 Hint:
 Thinking of using advanced data structures? You are thinking it too complicated.
 For each update operation, do you really need to update all elements between i and j?
 Update only the first and end element is sufficient.
 The optimal time complexity is O(k + n) and uses O(1) extra space.
 */

public class _370 {
    public static class Solution1 {
        public int[] getModifiedArray(int length, int[][] updates) {
            int[] nums = new int[length];
            int k = updates.length;
            for (int i = 0; i < k; i++) {
                int start = updates[i][0];
                int end = updates[i][1];
                int inc = updates[i][2];
                nums[start] += inc;
                if (end < length - 1) {
                    nums[end + 1] -= inc;
                }
            }

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

@@ -33,1044 +33,8 @@
 s;%0A%0A
-/**%0A * 370. Range Addition%0A *%0A * Assume you have an array of length n initialized with all 0's and are given k update operations.%0A * Each operation is represented as a triplet: %5BstartIndex, endIndex, inc%5D%0A * which increments each element of subarray A%5BstartIndex ... endIndex%5D (startIndex and endIndex inclusive) with inc.%0A * Return the modified array after all k operations were executed.%0A%0A Example:%0A%0A Given:%0A%0A length = 5,%0A updates = %5B%0A %5B1,  3,  2%5D,%0A %5B2,  4,  3%5D,%0A %5B0,  2, -2%5D%0A %5D%0A%0A Output:%0A%0A %5B-2, 0, 3, 5, 3%5D%0A Explanation:%0A%0A Initial state:%0A %5B 0, 0, 0, 0, 0 %5D%0A%0A After applying operation %5B1, 3, 2%5D:%0A %5B 0, 2, 2, 2, 0 %5D%0A%0A After applying operation %5B2, 4, 3%5D:%0A %5B 0, 2, 5, 5, 3 %5D%0A%0A After applying operation %5B0, 2, -2%5D:%0A %5B-2, 0, 3, 5, 3 %5D%0A%0A Hint:%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 */%0A%0A
 publ

refactor 370