Problem Statement

You are given an integer length and an array updates where updates[i] = [startIdi, endIdxi, inci].

You have an array of length with all zeroes, and you have some operation to apply on arr. In the ith operation, you should increment all the elements arr[startIdxi], arr[startIdxi + 1], …, arr[endIdxi] by inci.

Return arr after applying all the updates.

Constraints

1 <= length <= 10^5
0 <= updates.length <= 10^4
0 <= startIdxi <= endIdxi < length
-1000 <= inci <= 1000

Examples

Example 1:

Input: length = 5, updates = [
                              [1, 3, 2],
                              [2, 4, 3],
                              [0, 2, -2]
                             ]
Output: [-2, 0, 3, 5, 3]

Explanation:
Apply [1, 3, 2], arr = [0, 2, 2, 2, 0]
Apply [2, 4, 3], arr = [0, 2, 5, 5, 3]
Apply [0, 2, -2], arr = [-2, 0, 3, 5, 3]

Example 2:

Input: length = 10, updates = [[2,4,6],[5,6,8],[1,9,-4]]
Output: [0, -4, 2, 2, 2, 4, 4, -4, -4, -4]

Explanation:
Apply [2,4,6] → arr = [0, 0, 6, 6, 6, 0, 0, 0, 0, 0]
Apply [5,6,8] → arr = [0, 0, 6, 6, 6, 8, 8, 0, 0, 0]
Apply [1,9,-4] → arr = [0, -4, 2, 2, 2, 4, 4, -4, -4, -4]

Different Approaches

1️⃣ Brute Force Approach

Intuition:

The idea is to update specific ranges of an array multiple times based on the given updates. Each update consists of a start and end index, along with a value that needs to be added to all elements in that range. The simplest approach is to iterate through each update, and for each update, modify the array by incrementing the values in the specified range. This ensures that the values in the array are modified correctly after all updates are applied, resulting in the final array.

Approach:

1. Initialize a result array of the given length with all elements set to zero.
2. Loop through each update in the updates list.
3. For each update, extract the start index, end index, and the value to be added.
4. Apply the update by iterating through the elements from the start index to the end index and increment each element by the specified value.
5. Continue this process for all updates.
6. After processing all updates, return the final modified array as the result.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
        vector<int> result(length, 0);
        // Iterate through each update
        for (auto& tuple : updates) {
            int start = tuple[0], end = tuple[1], val = tuple[2];

            // update by incrementing values from start to end
            for (int i = start; i <= end; i++) {
                result[i] += val;
            }
        }
        return result;
    }
};
int main() {
    Solution sol;
    vector<vector<int>> updates = {{1, 3, 2}, {2, 4, 3}, {0, 2, -2}};
    int length = 5;

    vector<int> result = sol.getModifiedArray(length, updates);

    for (int val : result) {
        cout << val << " ";
    }
    cout << endl;
    return 0;
}

Complexity Analysis:

• Time Complexity:O(K * N ), where K is the number of updates and N is the length of the array.
  • For each update, the code iterates through the range from the start to the end index, resulting in this time complexity.
• Space Complexity:O(N), where N is the length of the result array.
  • This space is used to store the modified array. No additional significant space is used beyond this array.

2️⃣ Difference Array Technique (Optimal Approach)

Code:

class Solution {
public:
    vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
        // Step 1: Initialize a result array of size 'length' with all 0s.
        // This array will store the final modified values.
        vector<int> result(length, 0);

        // Step 2: Process each update in the 'updates' list.
        // Each update is of the form {startIndex, endIndex, value}
        for (auto query : updates) {
            int startIndex = query[0]; // starting index of the range
            int endIndex = query[1];   // ending index of the range
            int value = query[2];      // value to be added to all elements from startIndex to endIndex

            // Add the value at startIndex to mark the beginning of addition
            result[startIndex] += value;

            // Subtract the value at endIndex + 1 to mark the end of addition range
            // (only if endIndex + 1 is within array bounds)
            if (endIndex + 1 < length) {
                result[endIndex + 1] -= value;
            }
        }

        // Step 3: Convert the difference array to the final result
        // by calculating the prefix sum (cumulative sum)
        int cumulativeSum = 0;

        for (int i = 0; i < length; i++) {
            // Keep adding each value to cumulativeSum
            cumulativeSum += result[i];

            // Update the current index with the actual value
            result[i] = cumulativeSum;
        }

        // Step 4: Return the final modified array
        return result;
    }
};

Complexity Analysis:

• Time Complexity:O(N + K), where N is the length of the array and K is the number of updates.
  • The difference array approach ensures that each update is applied in constant time, and the final array is computed in a single pass.
• Space Complexity:O(N), where N is the length of the array.
  • This is the space required to store the result array.