Domain 2MediumCORE

Range Addition

We start with an array of zeros initialized to a specific length. We receive multiple update operations, each specifying a range [startIdx, endIdx] and a value inci (increment). For every operation, we must add inci to all elements within that inclusive range. Finally, we return the modified array.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Array

370. Range Addition

Model: qwen3.5:9b
Topics: Array
FAANG asked: 1
Acceptance rate: 63.7%


Problem Breakdown

We start with an array of zeros initialized to a specific length. We receive multiple update operations, each specifying a range [startIdx, endIdx] and a value inci (increment). For every operation, we must add inci to all elements within that inclusive range. Finally, we return the modified array.

Inputs:

  • An integer length: The size of our target array.
  • A list of lists updates: Each inner list contains [startIdx, endIdx, inc].

Outputs:

  • A single list representing the final state of the array after all updates are applied sequentially (order doesn’t matter for addition).

Constraints & Edge Cases:

  • Scale: Length can be up to 10510^5, and there can be up to 10410^4 updates. This suggests we cannot afford an operation that touches every element of the array repeatedly if ranges overlap significantly or are large. We need something better than iterating per range for each update.
  • Negative Values: inci can be negative, effectively decrementing values. The logic must handle subtraction naturally (adding a negative).
  • Empty Updates: If no updates exist, we should return an array of zeros.

Intuition

If I were to implement this naively, for each update [startIdx, endIdx, inc], I would loop from startIdx to endIdx and add inc to every element in that slice.

Naive Complexity: In the worst case (e.g., updates cover almost the whole array), a single operation takes O(N)O(N) time where NN is length. With KK operations, total complexity becomes O(K⋅N)O(K \cdot N). Given constraints (105×104=10910^5 \times 10^4 = 10^9 ops), this will exceed typical execution limits (usually around 10810^8 ops per second).

Key Insight: We are only interested in the change to values. When we increment a range [s, e], it affects index s immediately but stops affecting elements after e. Specifically:

  • At index startIdx, the value increases by inc. This is an “onset” of change.
  • Immediately after index endIdx (at endIdx + 1), this specific increment should stop contributing to subsequent indices. So, at endIdx + 1, we subtract inc.

This transforms a range update into two point updates: one addition and one subtraction. This is the Difference Array technique. Once all operations are recorded as these boundary changes, we can compute the final array values by taking the prefix sum of this difference array. The value at any index ii in the result will be exactly the cumulative sum of differences up to that point.

Approach

  1. Initialize a diff (difference) array with size length + 2. We allocate an extra buffer so we can safely decrement at endIdx + 1 without checking bounds for every update, which simplifies the loop logic in Python and avoids overhead of conditional checks inside the tight loop over updates.
    • Indices 00 to length - 1 correspond to our result array elements.
    • Index length is used as a “stop” marker (where we subtract). The extra index (+2) provides safety margin but strictly length + 1 would suffice for the logic; however, using + 2 ensures no out-of-bounds access even if input indices were slightly off or to simplify mental model.
    • We iterate through updates and apply these two point updates: add at start, subtract after end. This takes O(K)O(K) time where KK is number of updates.
  2. Compute the prefix sums over the diff array to get the actual values. We iterate from index 0 to length - 1, maintaining a running sum (current_val). At each step, add it to our result (or overwrite in place). This takes O(N)O(N) time where NN is length.
  3. Return the resulting list of integers.

Complexity Analysis

  • Time Complexity: O(K+N)O(K + N). We iterate through updates once (KK operations, each taking constant time), and then we perform a single pass over the array to compute prefix sums (NN iterations). Given constraints, this is optimal linear time relative to input size.
  • Space Complexity: O(N)O(N) for storing the difference array (or result array) of length length.

Solution

def getModifiedArray(length: int, updates: list[list[int]]) -> list[int]:
    # Initialize a zero-filled array with sufficient space to handle boundary logic easily.
    # We use size 'length + 2' so that we can safely decrement at endIdx + 1 
    # without checking bounds for every update (though strictly length is enough if checked).
    diff = [0] * (length + 2) 
    
    # Apply difference array logic: add inc at start, subtract inc after end.
    for s, e, v in updates:
        diff[s] += v
        # We use 'e' directly from input; ensure we don't go out of bounds 
        # if our buffer wasn't large enough, but here size + 2 handles it safely.
        # However, strictly speaking indices >= length are irrelevant for the final result array.
        diff[e + 1] -= v
        
    # Compute prefix sums to reconstruct actual values from differences.
    current_val = 0
    res = []
    
    # We only need up to 'length' elements in our output, 
    # so we iterate exactly that many times.
    for i in range(length):
        current_val += diff[i]
        res.append(current_val)
        
    return res

# Example usage matching the prompt:
# print(getModifiedArray(5, [[1,3,2],[2,4,3],[0,2,-2]])) 

Edge Cases Handled

  • Empty Updates: The loop over updates simply doesn’t execute. diff remains all zeros (or initialized to 0). Prefix sum results in an array of zeros, which is correct for no operations applied.
  • Negative Increments (inci < 0): Since we use standard addition/subtraction operators, adding a negative number correctly decrements the range values without special logic needed.
  • Boundary Ranges:
    • startIdx = 0: Handled naturally by array indexing starting at 0.
    • endIdx = length - 1: The decrement happens at index length. Since we iterate only up to length for the result, values beyond that don’t affect our output logic (and are ignored in prefix sum loop).
  • Single Element Range: If startIdx == endIdx, we