Prefix Sum — Range Addition II
↗ LeetCode: Range Addition II · Easy · pattern chapter →
Given matrix of zeros m × n and operations [a, b] that add 1 to every cell in [0, a) × [0, b), return the count of maximum-valued cells.
Example 1 — m=3, n=3, ops=[[2,2],[3,3]] → 4 (top-left 2×2 has value 2) Example 2 — m=3, n=3, ops=[] → 9Example 3 — m=3, n=3, ops=[[1,1]] → 1
Constraints — 1 ≤ m, n ≤ 4·10⁴; 0 ≤ ops.length ≤ 10⁴. Brute applies each update to the full grid — O(ops·m·n) = 10⁴·10⁴·10⁴ = 10¹² ops (dead). Track only the intersection of all mins — O(ops) = 10⁴ ops.
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 — Actually apply operations
O(#ops · m·n). Baseline.
Approach 2 — Intersection of all rectangles (canonical)
Insight. Every op starts at (0,0). The max-valued cells are the intersection of all rectangles — i.e., min(a) × min(b).
java
int maxCount(int m, int n, int[][] ops) {
for (int[] op : ops) { m = Math.min(m, op[0]); n = Math.min(n, op[1]); }
return m * n;
}Execution Trace
Step 1 / 3Initialize scan.
Complexity — Time O(#ops); Space O(1).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Simulate | O(#ops · m·n) | O(m·n) | baseline |
| Intersect rectangles | O(#ops) | O(1) | optimum |
When to use which
- All rectangles anchored at corner → intersection min trick.
- Arbitrary rectangle positions → 2D difference array.
AI Study CompanionBeta
Related problems
Was this page helpful?