LeetCode 370: Range Addition Solution in Python – A Step-by-Step Guide

Imagine you’ve got an array of zeros—like a blank slate—and a list of updates telling you to add values to specific ranges, like “add 2 from index 1 to 3.” Your job is to apply all these updates and reveal the final array. That’s the challenge of LeetCode 370: Range Addition, a medium-level problem that’s all about efficient range updates. Using Python, we’ll explore two solutions: the Best Solution—a difference array approach for O(n + k) efficiency—and an Alternative Solution—brute force at O(n*k). With examples, clear code breakdowns, and a friendly vibe, this guide will help you update that array. Let’s start adding!

What Is LeetCode 370: Range Addition?

LeetCode 370: Range Addition gives you a length n and a list of updates, where each update is a triplet [startIndex, endIndex, inc] indicating to add inc to all elements from startIndex to endIndex (inclusive) in an initially zero-filled array. Your task is to return the final array after applying all updates. It’s a problem that tests your ability to optimize range modifications!

Problem Statement

Input:

length: Integer representing the array length.
updates: List of [startIndex, endIndex, inc] triplets.

Output: List[int] - Final array after all updates.
Rules:

Initial array is all zeros.
For each update [startIndex, endIndex, inc], add inc to elements from startIndex to endIndex (inclusive).
Indices are 0-based.

Constraints

1 <= length <= 10⁵
0 <= updates.length <= 10⁴
0 <= startIndex <= endIndex < length
-1000 <= inc <= 1000

Examples

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

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

Initial: [0,0,0,0,0].
[1,3,2]: [0,2,2,2,0].
[2,4,3]: [0,2,5,5,3].
[0,2,-2]: [-2,0,3,5,3].

Input: length = 3, updates = [[0,1,1]]

Output: [1,1,0]

Initial: [0,0,0].
[0,1,1]: [1,1,0].

Input: length = 2, updates = []

Output: [0,0]

No updates, stays [0,0].

These show the range update process—let’s solve it!

Understanding the Problem: Updating Ranges Efficiently

To tackle LeetCode 370 in Python, we need to: 1. Start with an array of zeros of length n. 2. Apply each update by adding inc to the specified range. 3. Return the final array after all updates.

A naive approach might update each range directly, but that’s slow for many updates. Instead, we’ll use:

Best Solution: Difference array—O(n + k) time, O(n) space—fast and clever.
Alternative Solution: Brute force—O(n*k) time, O(n) space—simple but inefficient.

Let’s optimize with the best solution!

Best Solution: Difference Array

Why This Is the Best Solution

The difference array approach runs in O(n + k) time (n is length, k is number of updates) by marking only the start and end points of each update, then computing the final array with a single pass. It’s the most efficient—avoiding repeated updates across ranges by leveraging cumulative effects!

How It Works

Think of it like tracking changes:

Difference Array: Initialize array d where d[i] is the change at index i.
Update: For each [start, end, inc]:

Add inc at startIndex (d[start] += inc).
Subtract inc at endIndex+1 (d[end+1] -= inc) if in bounds.

Cumulative Sum: Compute running sum of d to get final array.
Result: Final array reflects all updates.

It’s like noting where values rise and fall, then summing up!

Step-by-Step Example

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

Initial: d = [0,0,0,0,0].
Update [1,3,2]:

d[1] += 2 → [0,2,0,0,0].
d[3+1] -= 2 → [0,2,0,0,-2].

Update [2,4,3]:

d[2] += 3 → [0,2,3,0,-2].
d[4+1] -= 3 → [0,2,3,0,-2] (end+1=5 out of bounds, skip).

Update [0,2,-2]:

d[0] -= 2 → [-2,2,3,0,-2].
d[2+1] += 2 → [-2,2,3,2,-2].

Cumulative Sum:

arr[0] = -2 → [-2].
arr[1] = -2 + 2 = 0 → [-2,0].
arr[2] = 0 + 3 = 3 → [-2,0,3].
arr[3] = 3 + 2 = 5 → [-2,0,3,5].
arr[4] = 5 - 2 = 3 → [-2,0,3,5,3].

Result: [-2,0,3,5,3].

For length = 3, updates = [[0,1,1]]:

d: [1,0,-1].
Sum: [1,1,0].

Code with Explanation

Here’s the Python code using a difference array:

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

        # Apply updates to difference array
        for start, end, inc in updates:
            diff[start] += inc  # Add increment at start
            if end + 1 < length:
                diff[end + 1] -= inc  # Subtract at end+1 if in bounds

        # Compute final array with running sum
        result = [0] * length
        result[0] = diff[0]
        for i in range(1, length):
            result[i] = result[i-1] + diff[i]

        return result

Explanation

Line 4: diff: Array to store changes, initially all zeros.
Lines 6-9: Apply updates:

Add inc at start index.
Subtract inc at end+1 if within bounds (marks range end).

Lines 11-15: Compute result:

First element is diff[0].
Each subsequent element is previous + diff[i] (running sum).

Time: O(n + k)—k updates, one O(n) pass.
Space: O(n)—diff and result arrays (could optimize to O(1) extra by modifying in-place).

This is like sketching the changes, then filling in—super fast!

Alternative Solution: Brute Force

Why an Alternative Approach?

The brute force solution runs in O(n*k) time by directly applying each update to all affected indices. It’s slower but straightforward—great for small inputs or understanding the basic process!

How It Works

Initialize: Start with zero array.
Update: For each [start, end, inc], add inc to every index in range.
Result: Return final array.

Step-by-Step Example

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

Initial: [0,0,0,0,0].
[1,3,2]: [0,2,2,2,0].
[2,4,3]: [0,2,5,5,3].
[0,2,-2]: [-2,0,3,5,3].
Result: [-2,0,3,5,3].

Code with Explanation

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

        # Apply each update directly
        for start, end, inc in updates:
            for i in range(start, end + 1):
                result[i] += inc

        return result

Explanation

Line 4: result: Zero-filled array.
Lines 6-8: For each update, add inc to all indices from start to end (inclusive).
Time: O(n*k)—k updates, each potentially O(n).
Space: O(n)—result array.

It’s like painting each range directly—simple but slow!

Comparing the Two Solutions

Difference Array (Best):

Time: O(n + k)—linear passes.
Space: O(n)—diff array.
Pros: Fast, scalable.
Cons: Less intuitive initially.

Brute Force (Alternative):

Time: O(n*k)—quadratic for many updates.
Space: O(n)—result array.
Pros: Easy to understand.
Cons: Slow for large k.

Difference array wins for efficiency!

Additional Examples and Edge Cases

length=1, updates=[[0,0,1]]: [1].
length=5, updates=[]: [0,0,0,0,0].
Large updates: Difference array scales better.

Both work, difference array is faster.

Complexity Breakdown

Difference Array:

Time: O(n + k).
Space: O(n).

Brute Force:

Time: O(n*k).
Space: O(n).

Difference array excels for performance.

Key Takeaways

Difference Array: Mark and sum—fast and smart!
Brute Force: Direct updates—clear but slow!
Ranges: Optimization is key.
Python Tip: Arrays rock—see [Python Basics](/python/basics).

Final Thoughts: Update That Range

LeetCode 370: Range Addition in Python is a range-update challenge. The difference array solution is the efficiency champ, while brute force builds intuition. Want more? Try LeetCode 303: Range Sum Query or LeetCode 1094: Car Pooling. Ready to add? Visit Solve LeetCode 370 on LeetCode (premium) and modify that array today!