Problem Description

The Range Addition problem asks you to efficiently apply a series of increment operations to an initially zeroed array.

You are given:

• An integer length representing the size of an array nums initialized with all zeros.
• A list of operations, where each operation is represented as a triplet [startIndex, endIndex, inc]:
• startIndex and endIndex (inclusive) are indices in the array.
• inc is the value to increment each element in the subarray nums[startIndex...endIndex].

• Each operation must be applied efficiently, as there may be many operations and the array can be large.
• There is only one valid output for a given input.

Thought Process

At first glance, a straightforward approach is to loop through each operation and increment every element in the specified range. However, this brute-force method is inefficient if the array or the number of operations is large, since each operation could take up to O(n) time, leading to a total time complexity of O(k * n) where k is the number of operations.

To optimize, we need a way to apply increments to ranges without looping through every element in each range. This leads us to the concept of a difference array, which allows range updates in constant time and then computes the final array using a prefix sum.

The key insight is: instead of updating every element in a range, we mark the start of the increment at startIndex and the end of the increment at endIndex + 1 (if within bounds). Then, a single pass at the end applies all increments cumulatively.

Solution Approach

We use the difference array technique to efficiently perform range updates:

1. Initialize: Create an array res of size length with all zeros.
2. Apply Operations: For each operation [start, end, inc]:
   • Add inc to res[start].
   • If end + 1 is within bounds, subtract inc from res[end + 1].
3. Build Final Array: Iterate through res and compute the prefix sum at each index. This will give the final modified array after all operations.

Example Walkthrough

Example Input:

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

1. Initial array: [0, 0, 0, 0, 0]
2. Apply [1, 3, 2]:
   • Add 2 at index 1: [0, 2, 0, 0, 0]
   • Subtract 2 at index 4: [0, 2, 0, 0, -2]
3. Apply [2, 4, 3]:
   • Add 3 at index 2: [0, 2, 3, 0, -2]
   • No subtraction at index 5 (out of bounds)
4. Apply [0, 2, -2]:
   • Add -2 at index 0: [-2, 2, 3, 0, -2]
   • Subtract -2 at index 3: [-2, 2, 3, 2, -2]
5. Prefix sum:
   • Index 0: -2
   • Index 1: -2 + 2 = 0
   • Index 2: 0 + 3 = 3
   • Index 3: 3 + 2 = 5
   • Index 4: 5 + (-2) = 3
   Final array: [-2, 0, 3, 5, 3]

Time and Space Complexity

Brute-force approach:

• Time: O(k * n) where k is the number of operations and n is the array length. Each operation may touch up to n elements.
• Space: O(n) for the result array.

• Time: O(k + n). Each operation is applied in O(1) time, and then a single O(n) prefix sum pass.
• Space: O(n) for the result array.

Summary

The Range Addition problem demonstrates how range updates can be made efficient using the difference array technique. By marking only the start and end+1 of each increment, we avoid redundant work. The final prefix sum sweep applies all increments in one pass, making the solution both elegant and optimal. This approach is a powerful tool for any scenario involving frequent range updates.

Code Implementation

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

vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
    vector<int> res(length, 0);
    for (const auto& u : updates) {
        int start = u[0], end = u[1], inc = u[2];
        res[start] += inc;
        if (end + 1 < length) res[end + 1] -= inc;
    }
    for (int i = 1; i < length; ++i) {
        res[i] += res[i - 1];
    }
    return res;
}
      

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

function getModifiedArray(length, updates) {
    const res = new Array(length).fill(0);
    for (const [start, end, inc] of updates) {
        res[start] += inc;
        if (end + 1 < length) res[end + 1] -= inc;
    }
    for (let i = 1; i < length; ++i) {
        res[i] += res[i - 1];
    }
    return res;
}