Range Addition
Medium · Arrays & Hashing · Explanation and code example
Difference Array and Prefix Sum
How it works
A range increment changes the running value at its start and undoes that change immediately after its end. Store only these two boundary differences for each update. One prefix-sum pass then reconstructs every final array value.
Steps
- Add the increment at start.
- Subtract it at end + 1 when that index exists.
- Prefix-sum the differences into the returned array.
Complexity
- Time: O(length + number of updates).
- Space: O(length).
Things to watch for
- Ranges include both endpoints.
- Negative increments work with the same boundaries.
- Return a concrete list in Python, rather than a lazy accumulate iterator.
Python code example
import itertools
class Solution:
def getModifiedArray(
self,
length: int,
updates: list[list[int]],
) -> list[int]:
line = [0] * length
for start, end, inc in updates:
line[start] += inc
if end + 1 < length:
line[end + 1] -= inc
return list(itertools.accumulate(line))
C++ code example
class Solution {
public:
vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
vector<int> ans;
vector<int> line(length);
int prefix = 0;
for (const vector<int>& update : updates) {
const int start = update[0];
const int end = update[1];
const int inc = update[2];
line[start] += inc;
if (end + 1 < length)
line[end + 1] -= inc;
}
for (const int diff : line) {
prefix += diff;
ans.push_back(prefix);
}
return ans;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.