LC:370 Range Addition.

Problem Statement

You are given an integer n and an array of m update operations, where each update operation is represented as a triplet:

[startIndex, endIndex, inc].

Initially, you have an array nums of length n filled with 0.

For each update [startIndex, endIndex, inc], add inc to each element of nums in the range startIndex <= i <= endIndex.

Return the final nums array after applying all the operations.

Example
Input:

n = 5
updates = [[1, 3, 2], [2, 4, 3], [0, 2, -2]]

Output:

[-2, 0, 3, 5, 3]

*Explanation:
*
`Start with [0, 0, 0, 0, 0]

Apply [1, 3, 2] → [0, 2, 2, 2, 0]

Apply [2, 4, 3] → [0, 2, 5, 5, 3]

Apply [0, 2, -2] → [-2, 0, 3, 5, 3]`

Approach (Difference Array + Prefix Sum)

A naive approach would update each element in [startIndex..endIndex] individually for every update, resulting in O(m * n) time.

Instead, we use a Difference Array:

For an update [l, r, inc], we do:

diff[l] += inc

diff[r + 1] -= inc (if r + 1 < n)

After all updates, we take the prefix sum of the diff array to construct the final nums.

This reduces the complexity toO(n + m).

C++ Solution Code

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

vector<int> getModifiedArray(int n, vector<vector<int>>& updates) {
    vector<int> diff(n, 0);

    // Apply difference array updates
    for (auto& u : updates) {
        int start = u[0], end = u[1], val = u[2];
        diff[start] += val;
        if (end + 1 < n) diff[end + 1] -= val;
    }

    // Build final array by taking prefix sums
    vector<int> result(n, 0);
    int runningSum = 0;
    for (int i = 0; i < n; i++) {
        runningSum += diff[i];
        result[i] = runningSum;
    }
    return result;
}

int main() {
    int n = 5;
    vector<vector<int>> updates = {{1, 3, 2}, {2, 4, 3}, {0, 2, -2}};
    vector<int> res = getModifiedArray(n, updates);

    cout << "Final Array: ";
    for (int x : res) cout << x << " ";
    cout << endl;
    return 0;
}

Complexity Analysis

Time Complexity: O(n + m)

Space Complexity: O(n)

Open Source Contribution

I am building an open-source repository of DSA solutions in C++, organized algorithm-wise for easier learning.
Feel free to explore, star ⭐, and contribute to my repository:
👉 DSA in C++ – GitHub Repository