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 , and there can be up to 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:
incican 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 time where is length. With operations, total complexity becomes . Given constraints ( ops), this will exceed typical execution limits (usually around 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 byinc. This is an “onset” of change. - Immediately after index
endIdx(atendIdx + 1), this specific increment should stop contributing to subsequent indices. So, atendIdx + 1, we subtractinc.
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 in the result will be exactly the cumulative sum of differences up to that point.
Approach
- Initialize a
diff(difference) array with sizelength + 2. We allocate an extra buffer so we can safely decrement atendIdx + 1without 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 to
length - 1correspond to our result array elements. - Index
lengthis used as a “stop” marker (where we subtract). The extra index (+2) provides safety margin but strictlylength + 1would suffice for the logic; however, using+ 2ensures 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 time where is number of updates.
- Indices to
- Compute the prefix sums over the
diffarray to get the actual values. We iterate from index 0 tolength - 1, maintaining a running sum (current_val). At each step, add it to our result (or overwrite in place). This takes time where is length. - Return the resulting list of integers.
Complexity Analysis
- Time Complexity: . We iterate through
updatesonce ( operations, each taking constant time), and then we perform a single pass over the array to compute prefix sums ( iterations). Given constraints, this is optimal linear time relative to input size. - Space Complexity: 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
updatessimply doesn’t execute.diffremains 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 indexlength. Since we iterate only up tolengthfor 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