Prefix Sum — Range Addition
↗ LeetCode: Range Addition · Medium · pattern chapter →
Asked atGoogleAmazon
Given length n and updates [start, end, val], return the array after applying all updates.
Example 1 — n=5, updates=[[1,3,2],[2,4,3],[0,2,-2]] → [-2,0,3,5,3]Example 2 — n=1, updates=[[0,0,5]] → [5]
Constraints — 1 ≤ n ≤ 10⁵; 0 ≤ updates.length ≤ 10⁴; inclusive ranges. Brute applies each update by writing every index — O(ops·n) = 10⁴·10⁵ = 10⁹ ops (TLE). Difference array + prefix sum is O(ops + n) = 1.1·10⁵ ops = <5 ms.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — Direct fill
O(n · m). Baseline.
Approach 2 — Difference array (canonical)
Insight. Each range update +val, -val at endpoints; single prefix scan recovers totals.
java
int[] getModifiedArray(int n, int[][] updates) {
int[] diff = new int[n + 1];
for (int[] u : updates) {
diff[u[0]] += u[2];
diff[u[1] + 1] -= u[2];
}
for (int i = 1; i < n; i++) diff[i] += diff[i - 1];
return Arrays.copyOf(diff, n);
}Execution Trace
Step 1 / 2sum of endpoint deltas
Complexity — Time O(n + m); Space O(n).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Direct fill | O(n·m) | O(n) | baseline |
| Diff array | O(n+m) | O(n) | optimum |
When to use which
- Static "many adds, one read" → diff array.
- Interleaved add + read → segment tree with lazy propagation.
- Multi-dim range add → 2D diff array (see Matrix Block Sum).
AI Study CompanionBeta
Related problems
Was this page helpful?
📚 Related problems