Range Addition

Try it yourself

MediumProblemExternal linkUpdated Oct 25, 2026

Description

You get an integer length and a list of updates. Start from an array of length zeros.

Each update is [start, end, inc]: add inc to every value from index start to index end, both included.

Return the array after all the updates have been applied.

Examples

Example 1

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

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

Explanation: After [1, 3, 2]: [0, 2, 2, 2, 0]. After [2, 4, 3]: [0, 2, 5, 5, 3]. After [0, 2, -2]: [-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: Indexes 2 to 4 get 6, indexes 5 and 6 get 8, and every index from 1 to 9 loses 4.

Example 3

Input: length = 3, updates = []

Output: [0,0,0]

Explanation: No updates, so the array stays all zeros.

Constraints

1 ≤ length ≤ 10^5
0 ≤ updates.length ≤ 10^4
0 ≤ start ≤ end < length
-1000 ≤ inc ≤ 1000

Editorial

Brute Force

Intuition

Do what each update says: walk its range and add inc to every index in it.

Step-by-Step Explanation

For length = 5 and updates = [[1, 3, 2], [2, 4, 3], [0, 2, -2]]:

Start from 5 zeros and apply each update to every index of its range.
Add 2 to indexes 1 to 3, one index at a time. That's 3 additions, 3 so far.
Add 3 to indexes 2 to 4, one index at a time. That's 3 additions, 6 so far.
Add −2 to indexes 0 to 2, one index at a time. That's 3 additions, 9 so far.
Done after 9 additions, since each update cost as much as its range is long.

Apply Each Update Cell by Cell — The shaded cells are the range of the update just applied.

Algorithm

Make result, length zeros.
For each update, add inc to result[start] through result[end].
Return result.

Code

class Solution {
public:
    vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
        vector<int> result(length, 0);
        for (const auto& u : updates)
            for (int i = u[0]; i <= u[1]; i++)  // every index of the range, one at a time
                result[i] += u[2];
        return result;
    }
};

class Solution:
    def getModifiedArray(self, length: int, updates: list[list[int]]) -> list[int]:
        result = [0] * length
        for start, end, inc in updates:
            for i in range(start, end + 1):     # every index of the range, one at a time
                result[i] += inc
        return result

class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        int[] result = new int[length];
        for (int[] u : updates)
            for (int i = u[0]; i <= u[1]; i++)  // every index of the range, one at a time
                result[i] += u[2];
        return result;
    }
}

var getModifiedArray = function(length, updates) {
    const result = new Array(length).fill(0);
    for (const [start, end, inc] of updates)
        for (let i = start; i <= end; i++)      // every index of the range, one at a time
            result[i] += inc;
    return result;
};

Complexity Analysis

Time Complexity: O(n · q)

Each of the q updates can cover all n indexes.

Space Complexity: O(1) beyond the answer.

Why This Approach Is Not Efficient

With 10^5 indexes and 10^4 updates that each cover the whole array, that's 10^9 additions (over the time limit in Python and javascript).

Inside a range, an update adds the same amount to every index, so the difference between neighbours doesn't change there. It changes in just two places: at start, where the values jump up by inc, and just after end, where they drop back.

Optimal Approach - Difference Array

Intuition

Keep diff, how much each value differs from the one before it. The running total of diff rebuilds the array. An update then needs two writes: diff[start] += inc and diff[end + 1] -= inc. The running total picks inc up at start, carries it through end, and drops it right after.

Give diff one spare slot at the end, so end + 1 is a valid index even when a range reaches the last value. Apply every update, then take the running total once.

Step-by-Step Explanation

For length = 5 and updates = [[1, 3, 2], [2, 4, 3], [0, 2, -2]]:

Each update writes twice into diff. Nothing else is touched until the end.
Update [1, 3, 2]. diff[1] gets 2 where the range starts, and diff[4] gets −2 just after it ends.
Update [2, 4, 3]. diff[2] gets 3 where the range starts, and diff[5] gets −3 just after it ends.
Update [0, 2, −2]. diff[0] gets −2 where the range starts, and diff[3] gets 2 just after it ends.
The running total adds diff[0] = −2, so result[0] is −2.
The running total adds diff[1] = 2, so result[1] is 0.
The running total adds diff[2] = 3, so result[2] is 3.
The running total adds diff[3] = 2, so result[3] is 5.
The running total adds diff[4] = −2, so result[4] is 3.
6 writes and one pass of 5, however long the ranges are.

Two Writes per Update, One Running Total — Top: diff, with its spare slot at the end. Bottom: the result, filled by the running total of diff.

Algorithm

Make diff, length + 1 zeros.
For each update, diff[start] += inc and diff[end + 1] -= inc.
Keep a running total of diff[0..length-1]; each running total is the next value of the result.

Code

class Solution {
public:
    vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
        vector<int> diff(length + 1, 0);        // one spare slot, so end + 1 is always a valid index
        for (const auto& u : updates) {
            diff[u[0]] += u[2];                 // the range starts here
            diff[u[1] + 1] -= u[2];             // and stops just after its last index
        }
        vector<int> result(length);
        int running = 0;
        for (int i = 0; i < length; i++) {
            running += diff[i];                 // the running total of the differences
            result[i] = running;
        }
        return result;
    }
};

class Solution:
    def getModifiedArray(self, length: int, updates: list[list[int]]) -> list[int]:
        diff = [0] * (length + 1)               # one spare slot, so end + 1 is always a valid index
        for start, end, inc in updates:
            diff[start] += inc                  # the range starts here
            diff[end + 1] -= inc                # and stops just after its last index
        result, running = [], 0
        for i in range(length):
            running += diff[i]                  # the running total of the differences
            result.append(running)
        return result

class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        int[] diff = new int[length + 1];       // one spare slot, so end + 1 is always a valid index
        for (int[] u : updates) {
            diff[u[0]] += u[2];                 // the range starts here
            diff[u[1] + 1] -= u[2];             // and stops just after its last index
        }
        int[] result = new int[length];
        int running = 0;
        for (int i = 0; i < length; i++) {
            running += diff[i];                 // the running total of the differences
            result[i] = running;
        }
        return result;
    }
}

var getModifiedArray = function(length, updates) {
    const diff = new Array(length + 1).fill(0); // one spare slot, so end + 1 is always a valid index
    for (const [start, end, inc] of updates) {
        diff[start] += inc;                     // the range starts here
        diff[end + 1] -= inc;                   // and stops just after its last index
    }
    const result = [];
    let running = 0;
    for (let i = 0; i < length; i++) {
        running += diff[i];                     // the running total of the differences
        result.push(running);
    }
    return result;
};

Complexity Analysis

Time Complexity: O(n + q)

Two writes per update, then one pass.

Space Complexity: O(n) for diff.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Taking inc off at end instead of after it. diff[end] -= inc

On length = 5, updates = [[1, 3, 2], [2, 4, 3], [0, 2, -2]], it returns [-2,0,5,3,0]; the answer is [-2,0,3,5,3]. end is the last index that gets inc, so the running total has to carry it through end and drop it one index later. Writing -inc at end itself cancels it one index too early: the last index of every range misses its update.

No spare slot at the end. diff = [0] * length

On length = 4, updates = [[3, 3, 7]], it crashes with IndexError: list index out of range; the answer is [0,0,0,7]. With exactly length slots, a range that ends on the last index writes -inc to diff[length], one past the end, and crashes. One spare slot at the end takes that write; it's never read into the answer.

Never taking inc back off. diff[start] += inc # and nothing else

On length = 5, updates = [[1, 2, 7]], it returns [0,7,7,7,7]; the answer is [0,7,7,0,0]. +inc at start alone makes the running total carry inc to the end of the array, not to the end of the range. The -inc just after end is what stops it.

Where This Pattern Is Taught

This problem practises the difference array: range updates as two writes and one running total. It's taught in Difference Arrays and 2D Prefix Sums.