Solution For Range Addition

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

“`

Step by Step Implementation For Range Addition

class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        int[] res = new int[length];
        for (int[] update : updates) {
            int value = update[2];
            int start = update[0];
            int end = update[1];
            res[start] += value;
            if (end < length - 1) {
                res[end + 1] -= value;
            }
        }
        for (int i = 1; i < length; i++) {
            res[i] += res[i - 1];
        }
        return res;
    }
}

class Solution:
    def getModifiedArray(self, length, updates):
        # Create list of zeros with length "length"
        arr = [0] * length

        # Iterate through updates
        for update in updates:
            # Set start index to value in update
            start = update[0]

            # Set end index to value in update
            end = update[1]

            # Set increment to value in update
            increment = update[2]

            # Iterate through arr from start to end
            for i in range(start, end + 1):
                # Add increment to each element in arr
                arr[i] += increment

        # Return modified arr
        return arr

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

// 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 ]

/**
 * @param {number} length
 * @param {number[][]} updates
 * @return {number[]}
 */
var getModifiedArray = function(length, updates) {
    let res = new Array(length).fill(0);
    for (let i = 0; i < updates.length; i++) {
        let start = updates[i][0];
        let end = updates[i][1];
        let inc = updates[i][2];
        for (let j = start; j <= end; j++) {
            res[j] += inc;
        }
    }
    return res;
};

class Solution {
public:
    vector getModifiedArray(int length, vector>& updates) {
        vector res(length);
        for (auto &update : updates) {
            int value = update[2];
            int start = update[0];
            int end = update[1];
            res[start] += value;
            if (end < length - 1) {
                res[end + 1] -= value;
            }
        }
        for (int i = 1; i < length; ++i) {
            res[i] += res[i - 1];
        }
        return res;
    }
};

class Solution { 
    public int[] GetModifiedArray(int length, int[][] updates) { 
        int[] res = new int[length]; 
        foreach (int[] update in updates) { 
            int value = update[2]; 
            int start = update[0]; 
            int end = update[1]; 
            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; 
    } 
}