LeetCode 370: Range Addition

Problem Restatement

We are given an array of length length.

Initially, every element is 0.

We are also given a list of update operations. Each update has this form:

[startIndex, endIndex, inc]

For each update, add inc to every index from startIndex to endIndex, inclusive.

After all updates are applied, return the final array.

The update range is inclusive, and the official example is length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]], with output [-2,0,3,5,3].

Input and Output

Example function shape:

def getModifiedArray(length: int, updates: list[list[int]]) -> list[int]:
    ...

Examples

Example:

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

Start with:

[0, 0, 0, 0, 0]

Apply the first update:

[1, 3, 2]

Add 2 from index 1 to index 3:

[0, 2, 2, 2, 0]

Apply the second update:

[2, 4, 3]

Add 3 from index 2 to index 4:

[0, 2, 5, 5, 3]

Apply the third update:

[0, 2, -2]

Add -2 from index 0 to index 2:

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

So the answer is:

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

First Thought: Apply Each Update Directly

The most direct solution is to keep the array and apply every update element by element.

class Solution:
    def getModifiedArray(self, length: int, updates: list[list[int]]) -> list[int]:
        nums = [0] * length

        for start, end, inc in updates:
            for i in range(start, end + 1):
                nums[i] += inc

        return nums

This is easy to understand.

But it can be slow.

If there are many updates and each update covers a large range, the same indices are updated again and again.

With m updates and array length n, this can take:

O(m * n)

We need to avoid touching every element for every update.

Key Insight

Use a difference array.

Instead of applying an increment to every index in a range, mark where the increment starts and where it stops.

For an update:

[start, end, inc]

we do:

diff[start] += inc

This means:

from this index onward, add inc

Then, if end + 1 is inside the array:

diff[end + 1] -= inc

This means:

after the range ends, cancel inc

After all updates are marked, the final array is the prefix sum of diff.

Difference Array Example

Use:

length = 5
updates = [[1, 3, 2]]

Start with:

diff = [0, 0, 0, 0, 0]

Mark the start:

diff[1] += 2

Now:

[0, 2, 0, 0, 0]

Mark the position after the end:

diff[4] -= 2

Now:

[0, 2, 0, 0, -2]

Take prefix sums:

Final array:

[0, 2, 2, 2, 0]

That is exactly the direct update result.

Algorithm

1. Create a difference array:

diff = [0] * length

2. For each update [start, end, inc]:

   • Add inc at start.
   • Subtract inc at end + 1 if that index exists.

3. Convert the difference array into the final array by prefix sum.

4. Return the final array.

Correctness

For each update [start, end, inc], the algorithm adds inc to diff[start].

When we later compute prefix sums, this inc contributes to every index from start onward.

If end + 1 is inside the array, the algorithm subtracts inc at diff[end + 1].

During prefix-sum reconstruction, this subtraction cancels the earlier increment starting at end + 1.

Therefore, the update contributes exactly inc to indices from start through end, and contributes 0 outside that range.

Because addition is commutative, all range updates can be marked first and then combined with one prefix sum pass.

So the final array produced by the algorithm is exactly the array obtained by applying every update directly.

Complexity

Let:

This improves over the direct O(n * m) approach.

Implementation

class Solution:
    def getModifiedArray(self, length: int, updates: list[list[int]]) -> list[int]:
        diff = [0] * length

        for start, end, inc in updates:
            diff[start] += inc

            if end + 1 < length:
                diff[end + 1] -= inc

        running = 0

        for i in range(length):
            running += diff[i]
            diff[i] = running

        return diff

Code Explanation

We create the difference array:

diff = [0] * length

For every update, mark the start of the increment:

diff[start] += inc

Then mark where the increment should stop:

if end + 1 < length:
    diff[end + 1] -= inc

The boundary check matters when the update reaches the final index.

For example:

[start, end, inc] = [2, 4, 3]
length = 5

The range ends at index 4, so end + 1 = 5 is outside the array. There is no later index where we need to cancel the increment.

Then we build the final array with a running prefix sum:

running = 0

for i in range(length):
    running += diff[i]
    diff[i] = running

We reuse diff as the output array to avoid allocating another list.

Testing

def run_tests():
    s = Solution()

    assert s.getModifiedArray(
        5,
        [[1, 3, 2], [2, 4, 3], [0, 2, -2]],
    ) == [-2, 0, 3, 5, 3]

    assert s.getModifiedArray(
        10,
        [[2, 4, 6], [5, 6, 8], [1, 9, -4]],
    ) == [0, -4, 2, 2, 2, 4, 4, -4, -4, -4]

    assert s.getModifiedArray(
        3,
        [],
    ) == [0, 0, 0]

    assert s.getModifiedArray(
        1,
        [[0, 0, 5], [0, 0, -2]],
    ) == [3]

    assert s.getModifiedArray(
        5,
        [[0, 4, 10]],
    ) == [10, 10, 10, 10, 10]

    print("all tests passed")

run_tests()

Test meaning: