Range Addition - Leetcode Solution

Problem statement: You are given an integer length and an array updates where updates[i] = [startIdxi, endIdxi, inci].

You have an array arr of length length with all zeros, and you have some operation to apply on arr. In the ith operation, you apply inci to all the elements from startIdxi to endIdxi (inclusive) of arr. Operations are performed in order of their index i (0-indexed).

Return the modified array after all k operations.

Detailed solution: The problem asks us to apply a certain operation to an array for a given range of indices. We can apply all these operations at once if we have all the ranges with updates in one array. Therefore, the first step is to convert the given input into an array of updates.

We can then iterate through the updates array and apply the update to the output array. To do this efficiently, we can calculate the prefix sum of the updates array. This will give us the amount to add to each element in the output array. We can then update the output array using this prefix sum array.

The prefix sum array can be calculated using dynamic programming. At each index i in the updates array, we add the value of the previous update to the current update. This gives us the prefix sum array.

Once we have the prefix sum array, we can use it to update the output array. We iterate through the prefix sum array and add the value at each index to the output array. This gives us the modified output array after all the updates.

Time Complexity: The time complexity of this solution is O(n + k), where n is the length of the input array and k is the number of updates.

Space Complexity: The space complexity of this solution is O(n), where n is the length of the input array.

Code:

def getModifiedArray(length: int, updates: List[List[int]]) -> List[int]:
    arr = [0] * length
    
    for start, end, inc in updates:
        arr[start] += inc
        if end < length - 1:
            arr[end + 1] -= inc
    
    prefix_sum = [0] * length
    prefix_sum[0] = arr[0]
    for i in range(1, length):
        prefix_sum[i] = prefix_sum[i - 1] + arr[i]
    
    return prefix_sum

1