LeetCode 370 - Range Addition

LeetCode Problem 370

Difficulty: 🟡 Medium
Topics: Array, Prefix Sum

Solution

Problem Understanding

The problem gives us an initially zero-filled array of size length. We are also given a list of update operations, where each update has the form:

[startIdx, endIdx, inc]

This means we must add inc to every element in the inclusive range from startIdx to endIdx.

For example, if the array is:

[0, 0, 0, 0, 0]

and we apply:

[1, 3, 2]

then every index from 1 through 3 increases by 2, producing:

[0, 2, 2, 2, 0]

The goal is to return the final array after all update operations have been applied.

The important detail is that updates affect ranges, not single positions. A naive implementation would explicitly iterate through every index inside every range and modify the array directly. However, the constraints make that potentially expensive.

The constraints are:

• length <= 10^5
• updates.length <= 10^4

A single update could affect nearly the entire array. In the worst case, a brute-force solution could perform:

10^4 * 10^5 = 10^9

operations, which is far too slow.

The constraints strongly suggest that we need a more efficient range update strategy.

Several edge cases are important:

• The updates array may be empty, in which case the result should remain all zeros.
• Updates may contain negative increments.
• A range may consist of a single element where startIdx == endIdx.
• Updates may touch the beginning or end of the array, which creates boundary handling concerns.
• Multiple updates may overlap heavily, so the algorithm must combine them efficiently.

Approaches

Brute Force Approach

The most direct solution is to simulate every update exactly as described.

For each update:

[startIdx, endIdx, inc]

we iterate from startIdx through endIdx and add inc to every element.

This approach is straightforward and obviously correct because it directly performs the required modifications.

However, its performance is poor. If each update spans most of the array, then each operation costs O(length). Since there may be up to 10^4 updates, the total runtime becomes:

O(updates * length)

which can reach 10^9 operations.

That is too slow for the problem constraints.

Optimal Approach, Difference Array with Prefix Sum

The key observation is that we do not actually need to update every element immediately.

Suppose we want to add 5 to every element from index 2 to index 6.

Instead of modifying all positions individually, we can record:

• At index 2, the effect starts, so add +5
• After index 6, the effect stops, so add -5 at index 7

Later, when we compute a running prefix sum, all indices between 2 and 6 automatically include the increment.

This technique is called a difference array.

For each update:

[start, end, inc]

we do:

diff[start] += inc
diff[end + 1] -= inc

if end + 1 is inside bounds.

After processing all updates, we compute the prefix sum of the difference array. The running total reconstructs the final modified array.

This transforms range updates from expensive O(range length) operations into constant time O(1) operations.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m × n)	O(1) extra	Explicitly updates every index in every range
Optimal	O(m + n)	O(n)	Uses difference array and prefix sums

Here:

• n = length
• m = len(updates)

Algorithm Walkthrough

1. Create a difference array of size length, initialized with zeros.

The difference array stores how the running value changes at each index, rather than storing the final values directly. 2. Process each update operation.

For an update:

[start, end, inc]

add inc at start.

This marks the beginning of the increment effect. 3. Mark where the increment effect ends.

If end + 1 is still inside the array bounds, subtract inc at end + 1.

This cancels the effect after the range ends. 4. After all updates are processed, compute the prefix sum.

Traverse the difference array from left to right while maintaining a running sum.

The running sum represents the actual value at each index in the final array. 5. Store the running totals back into the array and return it.

Why it works

The difference array records changes in value rather than absolute values.

Whenever we encounter a positive increment at some index, all future prefix sums include that increment. When we later encounter the corresponding negative decrement, the effect is canceled for subsequent indices.

Thus, every update affects exactly the intended interval and no others.

The prefix sum reconstruction guarantees that all overlapping updates combine correctly.

Python Solution

from typing import List

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

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

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

        running_sum = 0

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

        return diff

The implementation begins by creating the difference array named diff.

During the first loop, each update modifies only two positions:

• The start of the range
• The position immediately after the range

This efficiently encodes the range modification without touching every element.

The boundary check:

if end + 1 < length:

is important because the decrement position may fall outside the array when the update reaches the final index.

After all updates are recorded, the second loop computes the prefix sum. The variable running_sum accumulates the active increments at each position.

As we move through the array:

running_sum += diff[i]

the current running total becomes the actual value for index i.

Finally, the reconstructed array is returned.

Go Solution

func getModifiedArray(length int, updates [][]int) []int {
    diff := make([]int, length)

    for _, update := range updates {
        start := update[0]
        end := update[1]
        increment := update[2]

        diff[start] += increment

        if end+1 < length {
            diff[end+1] -= increment
        }
    }

    runningSum := 0

    for i := 0; i < length; i++ {
        runningSum += diff[i]
        diff[i] = runningSum
    }

    return diff
}

The Go implementation follows the same logic as the Python version.

A slice created with:

make([]int, length)

is automatically initialized with zeros.

Go slices are mutable, so the difference array can be updated directly.

The boundary condition is handled identically:

if end+1 < length

Go uses explicit variable declarations and indexed access, but the overall algorithm remains unchanged.

Integer overflow is not a concern under the given constraints because the values remain comfortably within Go's standard integer range.

Worked Examples

Example 1

Input:

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

Initial difference array:

Index	0	1	2	3	4
diff	0	0	0	0	0

Process Update [1, 3, 2]

Add +2 at index 1.

Subtract 2 at index 4.

Index	0	1	2	3	4
diff	0	2	0	0	-2

Process Update [2, 4, 3]

Add +3 at index 2.

Since 4 + 1 = 5 is outside bounds, no subtraction occurs.

Index	0	1	2	3	4
diff	0	2	3	0	-2

Process Update [0, 2, -2]

Add -2 at index 0.

Subtract -2 at index 3, which means add +2.

Index	0	1	2	3	4
diff	-2	2	3	2	-2

Compute Prefix Sum

Index	diff value	Running Sum	Final Value
0	-2	-2	-2
1	2	0	0
2	3	3	3
3	2	5	5
4	-2	3	3

Final result:

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

Example 2

Input:

length = 10
updates = [[2,4,6],[5,6,8],[1,9,-4]]

Initial difference array:

[0,0,0,0,0,0,0,0,0,0]

Process Update [2, 4, 6]

[0,0,6,0,0,-6,0,0,0,0]

Process Update [5, 6, 8]

[0,0,6,0,0,2,0,-8,0,0]

Process Update [1, 9, -4]

No subtraction occurs because 9 + 1 is outside bounds.

[0,-4,6,0,0,2,0,-8,0,0]

Compute Prefix Sum

Index	Running Sum
0	0
1	-4
2	2
3	2
4	2
5	4
6	4
7	-4
8	-4
9	-4

Final result:

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

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m + n)	Each update is processed once, then one prefix sum pass is performed
Space	O(n)	The difference array stores one value per index

Here:

• m = len(updates)
• n = length

The optimality comes from avoiding repeated work across overlapping ranges. Instead of updating every affected element individually, each update modifies only two positions, and the prefix sum reconstruction efficiently propagates those changes across the array.

Test Cases

from typing import List

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

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

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

        running_sum = 0

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

        return diff

solution = Solution()

# Provided example 1
assert solution.getModifiedArray(
    5,
    [[1, 3, 2], [2, 4, 3], [0, 2, -2]]
) == [-2, 0, 3, 5, 3]

# Provided example 2
assert solution.getModifiedArray(
    10,
    [[2, 4, 6], [5, 6, 8], [1, 9, -4]]
) == [0, -4, 2, 2, 2, 4, 4, -4, -4, -4]

# No updates, array remains zeros
assert solution.getModifiedArray(
    4,
    []
) == [0, 0, 0, 0]

# Single element array
assert solution.getModifiedArray(
    1,
    [[0, 0, 5]]
) == [5]

# Single range covering entire array
assert solution.getModifiedArray(
    5,
    [[0, 4, 3]]
) == [3, 3, 3, 3, 3]

# Negative increment
assert solution.getModifiedArray(
    5,
    [[1, 3, -2]]
) == [0, -2, -2, -2, 0]

# Multiple overlapping updates
assert solution.getModifiedArray(
    5,
    [[0, 2, 1], [1, 4, 2], [2, 3, 3]]
) == [1, 3, 6, 5, 2]

# Update ending at final index
assert solution.getModifiedArray(
    6,
    [[2, 5, 4]]
) == [0, 0, 4, 4, 4, 4]

# Multiple single-index updates
assert solution.getModifiedArray(
    5,
    [[1, 1, 3], [2, 2, 4], [3, 3, -1]]
) == [0, 3, 4, -1, 0]

Test	Why
Example 1	Validates overlapping updates with positive and negative increments
Example 2	Tests multiple large ranges and boundary handling
Empty updates	Ensures unchanged zero array is returned
Single element array	Tests smallest valid input size
Full array update	Verifies updates spanning entire array
Negative increment	Confirms subtraction works correctly
Overlapping updates	Ensures cumulative effects combine properly
Update reaching end	Validates boundary check for end + 1
Single-index updates	Tests ranges where start == end

Edge Cases

Empty Updates Array

If updates is empty, no modifications should occur. A buggy implementation might assume at least one update exists or mishandle the prefix sum reconstruction.

This implementation handles the case naturally because the update loop simply does nothing. The prefix sum over an all-zero difference array still produces all zeros.

Update Ending at the Final Index

When an update affects the last index in the array, there is no valid position at end + 1.

For example:

[2, 5, 4]

in an array of length 6.

A common bug is attempting:

diff[end + 1] -= increment

without checking bounds, which would cause an out-of-range error.

The implementation prevents this with:

if end + 1 < length:

Negative Increment Values

Updates may decrease values rather than increase them.

For example:

[1, 3, -2]

A poorly designed solution might incorrectly assume increments are always positive.

The difference-array technique works equally well with negative numbers because prefix sums naturally propagate both positive and negative changes.

Single-Element Ranges

An update may target exactly one index:

[start, start, inc]

A bug-prone implementation might incorrectly skip the range or mishandle the stopping point.

The difference-array method handles this cleanly because:

diff[start] += inc
diff[start + 1] -= inc

creates an effect lasting for exactly one position.