[LeetCode] Range Addition

Problem: 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: n = 5, updates = [[1,3,2], [2,4,3],[0,2,-2]
Output: [-2,0,3,5,3]
Explanation: Initial Array is [0,0,0,0,0]. Update [1,3,2] will make the array [0,2,2,2,0]. Update [2,4,3] will make array [0,2,5,5,3] and the last update [0,2,-2] will make the array [-2,0,3,5,3].

Approach: The obvious brute force approach would be to apply updates one by one but that is expensive as it can take O(n * k) time. Let's try to do better than this.

Here is the intuition of the approach:

• There is only one read query on the entire range, and it occurs at the end of all update queries. Additionally, the order of processing update queries is irrelevant as all the updates are addition only. Therefore, we don’t have to process the entire range until the end of the updates.
• Cumulative sums operations apply the effects of past elements to the future elements in the sequence.

What we are trying to do here, we are kind of marking the given range that we need to add this element from start to end and in the end we will just calculate the cumulative sum. Here are the steps which we do for every update [start, end, inc]:

1. arr[start]+= inc
2. arr[end + 1] -= inc

and in the end we need to apply the cumulative sum:

• FOR i = 1...n-1
• arri[i] += arr[i-1]

In this way we are kind of marking start, end  and inc. if you see when we take the cumulative sum it will update the array from start to end by adding inc and as we don't want to add inc after end index, we just added -inc to nullify it while calculating cumulative sum. 

Let's see from the above example. Initial array is [0,0,0,0,0]. Say there was only one update which is [1,3,2]. Let's apply our steps:

• arr[1] += 2
• arr[4] -= 2

so the array now becomes [0,2,0,0,-2]. Now once we apply cumulative sum step the array will become [0,2,2,2,0] which is what we wanted. In the same way if we apply all the updates and then apply the cumulative sum step it will give us the desired result.

Implementation in C#:

    public int[] GetModifiedArray(int length, int[][] updates) 

    {

        int[] result = new int[length];

        foreach (int[] update in updates) 

        {

            int start = update[0];

            int end = update[1];

            int inc = update[2];           

            result[start] += inc;

            if (end + 1 < length) 

            {

                result[end + 1] += -inc;

            }

        }

        for (int i = 1; i < length; i++) 

        {

            result[i] += result[i -1];

        } 

        return result;

    }

Complexity: O(k + n)