p32 — Range Sum Query 2D — Immutable

Source: LeetCode 304 · Medium · Topics: Array, Matrix, Prefix Sum, Design Companies (2024–2025 frequency): Microsoft (high), Amazon (high), Bloomberg (medium), Google (medium), Meta (medium) Loop position: algorithm round, often a “design + algorithm” hybrid because you must implement a class.

1. Quick Context

Design a class NumMatrix that:

• is initialized with an R × C integer matrix,
• supports sumRegion(r1, c1, r2, c2) returning the sum of the subrectangle with corners (r1, c1) and (r2, c2) inclusive.

The matrix is immutable (no updates), and sumRegion may be called many times. The point of the problem: precompute once, query in O(1).

The technique is the 2D extension of prefix sums + inclusion-exclusion: $$\text{sum}(r_1, c_1, r_2, c_2) = P[r_2{+}1][c_2{+}1] - P[r_1][c_2{+}1] - P[r_2{+}1][c_1] + P[r_1][c_1]$$ where P[r][c] = sum of the rectangle from (0,0) to (r-1, c-1) inclusive. The +1 border avoids special-casing the top row and left column.

Why the “+1 border” matters in interviews: it cleanly eliminates the if r1 == 0 or c1 == 0: branches that drown candidates in off-by-one bugs. Allocate (R+1) × (C+1) initialized to 0; the first row and column stay zero forever. Senior signal: do this without prompting.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/range-sum-query-2d-immutable/

STOP. 20-min timer. The 1D version (LC 303) is trivial; the 2D variant with inclusion-exclusion is where candidates trip on signs and off-by-ones.

3. Prerequisite Concepts

• 1D prefix sum.
• Inclusion-exclusion principle (basic 2-set version).
• OOP basics: __init__, instance state, method.

4. How to Approach (FRAMEWORK Steps 1–9)

Step 1 — Restate: “Design a class that, given an immutable matrix, answers arbitrary rectangular sum queries in O(1) each, after preprocessing.”

Step 2 — Clarify:

• “Will sumRegion be called many times?” (Yes, that’s the whole point.)
• “Is the matrix non-empty?” (Yes per spec — R≥1, C≥1.)
• “Inclusive bounds?” (Yes — both corners inclusive.)
• “r1 ≤ r2 and c1 ≤ c2?” (Yes — guaranteed.)
• “Values can be negative?” (Yes.)
• “Updates?” (No — immutable. LC 308 is the mutable variant — that’s Fenwick tree territory.)

Step 3 — Constraints: R, C ≤ 200, sumRegion calls ≤ 10⁴. With O(R·C) preprocessing and O(1) queries, this is trivial. The KEY metric isn’t raw N — it’s TOTAL work over many queries: O(R·C + Q).

Step 4 — Examples:

• LC canonical: matrix = [[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]
  • sumRegion(2, 1, 4, 3) → 8
  • sumRegion(1, 1, 2, 2) → 11
  • sumRegion(1, 2, 2, 4) → 12

Step 5 — Brute Force: Recompute sum in O((r2-r1+1)·(c2-c1+1)) per query. Acceptable for one query, but Q queries makes it O(Q·R·C) — way too slow when Q is large.

Step 6 — Complexity: Preprocessing O(R·C). Query O(1). Space O(R·C).

Step 7 — Pattern Recognition:

• “Many queries on immutable data, each query is an aggregate over a range” → precompute aggregate structure, query in O(1) or O(log).
• “Aggregate is sum” → prefix sums (additive group, supports subtraction).
• “Aggregate is min/max” → sparse table or segment tree (idempotent).

Step 8 — Develop: see solution.py.

Step 9 — Test: 1×1, single row, single column, full matrix, negative values, all-zero.

5. Progressive Hints

If stuck for 5 min, open hints.md.

6. Deeper Insight — Inclusion-exclusion and the “+1 border”

6.1 What P[r][c] represents

Define P[r][c] = sum of matrix[i][j] for all 0 ≤ i < r and 0 ≤ j < c. (Note the strict < — this is the “+1 border” convention.) So P[0][*] = 0 and P[*][0] = 0 for free.

Build with the 2D recurrence (also inclusion-exclusion): $$P[r][c] = \text{matrix}[r-1][c-1] + P[r-1][c] + P[r][c-1] - P[r-1][c-1]$$ The double-counted overlap P[r-1][c-1] is subtracted once.

6.2 Querying with inclusion-exclusion

To query the rectangle from (r1, c1) to (r2, c2) inclusive:

• Start with P[r2+1][c2+1] — sum of everything “above and to the left of” (r2+1, c2+1), i.e., the rectangle (0,0)-(r2,c2).
• Subtract P[r1][c2+1] — the rectangle above our target row range.
• Subtract P[r2+1][c1] — the rectangle left of our target column range.
• Add back P[r1][c1] — the top-left rectangle was double-subtracted.

6.3 Why the “+1 border”

Without it, P is R × C and the indices in the query become r2, r1-1, c2, c1-1. When r1 == 0 or c1 == 0, you must skip the subtractions — that’s a branch. With the border (P is (R+1) × (C+1)), P[0][*] = P[*][0] = 0 handles those cases naturally. Fewer bugs, less code.

6.4 Generalizations

• Difference array (1D): the dual operation. If you want to do many range updates and one final point query, use a difference array (add +x at l, -x at r+1; final prefix sum gives the answer).
• Range update + range query, mutable: Fenwick tree (BIT) with lazy propagation, or segment tree.
• 2D mutable point update + range query: 2D Fenwick tree, O(log²(N)) per op.
• 2D range update + 2D range query: four 2D BITs (classical Sherman trick). Heavy machinery — rare in interviews.

The interview lesson: knowing this hierarchy lets you instantly classify problems and pick the right structure.

7. Anti-Pattern Analysis

1. No “+1 border” → off-by-one bugs galore. Allocate (R+1) × (C+1). Period.
2. Storing only row-prefix-sums (not 2D). Then query is O(R) per call (sum across rows). Works but suboptimal.
3. Recomputing in sumRegion. Defeats the purpose.
4. Building P lazily inside sumRegion. Pay the build cost on first query; later queries are O(1). Works but breaks the “predictable latency” guarantee.
5. Wrong inclusion-exclusion signs. Memorize: +full - top - left + topleft. Practice this on a 3×3 grid by hand once.
6. Modifying the input matrix in-place. The spec says immutable; some templates use the input matrix’s first row/column as scratch — fine for performance, terrible for API hygiene.
7. Not validating r1 ≤ r2, c1 ≤ c2. LC guarantees this; production code should validate at the boundary.
8. Returning int when the sum could overflow (in Java/C++). Use long. Python is fine.

8. Skills & Takeaways

• 2D prefix sum + inclusion-exclusion — burn this template.
• “+1 border” trick — same trick recurs in segment trees, Fenwick trees, KMP failure function.
• “Preprocess once, query in O(1)” — recognize this as a design pattern, not a one-off.
• Class/method API design in algorithm interviews.
• Difference array (dual) as a related tool.

9. When to Move On

Move on when:

• You can write the class with “+1 border” in under 10 min.
• You can recite the inclusion-exclusion formula from memory.
• Your stress test passes 200 random queries vs brute.
• You can pivot to LC 1314 (Matrix Block Sum) using the same prefix sum.
• You can sketch the difference-array dual for “many range updates, one query.”

10. Company Context

Microsoft:

• A frequent “design class” warmup. Bar Raiser will probe with: “now make it mutable — what’s the data structure?” (Answer: 2D Fenwick tree or segment tree.)
• Scorecard phrase: “Design + Algorithm — 2D prefix sum class with inclusion-exclusion.”

Amazon:

• Common “Day 1” or warmup question in algo loops. The Bar Raiser cares about clean API + O(1) query proof.
• Scorecard phrase: “Strong — recognized precompute-once pattern.”

Bloomberg:

• Natural fit for financial dashboards: precompute cumulative P&L over a 2D (time, asset) grid; query any window in O(1).
• Scorecard phrase: “Pragmatic — recognized 2D cumulative aggregation.”

Google:

• Often paired with the mutable version (LC 308) as the senior follow-up. 2D Fenwick tree expected.
• Scorecard phrase: “Algorithm — immutable solution + Fenwick tree for mutable variant.”

Meta:

• Less common but appears when the loop is design-heavy. Focus on API correctness and complexity guarantees.
• Scorecard phrase: “Design — immutable structure with deterministic O(1) queries.”

11. Interviewer’s Lens

12. Level Delta

Mid (L4):

• 2D prefix sum solution with the “+1 border.”
• Correct inclusion-exclusion.
• O(R·C) build, O(1) query.

Senior (L5):

• Same + clean class API.
• Explains the “+1 border” rationale.
• Tests boundary cases (single row, single column, full matrix).

Staff (L6):

• Connects to the mutable variant (LC 308) and outlines 2D Fenwick tree.
• Discusses memory: if R, C are huge (say 10⁶ each), storing P is 10¹² entries — infeasible. Suggests sparse representation or block decomposition.
• Discusses the difference-array dual.

Principal (L7+):

• Discusses GPU-friendly variant: prefix sum (scan) is a classic parallel algorithm (Blelloch scan, work-efficient, O(N) work, O(log N) depth). 2D prefix sum is row-then-column scans.
• Discusses out-of-core: for matrices that don’t fit in RAM (e.g., satellite imagery cumulative-band sums), tile the prefix sum with summary blocks (similar to integral image pyramids in image processing).
• Discusses production: integral image in OpenCV (Viola-Jones face detection), summed-area tables in graphics, billing systems for arbitrary-window aggregations.

13. Follow-up Q&A

Q1: Mutable variant — point updates allowed. A: 2D Fenwick tree. Build O(R·C·log²). Update O(log² N). Query O(log² N). For range updates + range queries, four 2D Fenwick trees (Sherman trick) or 2D segment tree with lazy propagation.

Q2: Memory is tight — can we avoid the auxiliary array? A: Yes, build in-place by adding to the original matrix (mutates input). Saves O(R·C) memory but breaks immutability contract. In Python, NOT recommended (lists are mutable but the input is the caller’s responsibility); in C++ with explicit ownership, sometimes acceptable.

Q3: Range max/min query in 2D — same precompute trick? A: No — min/max are not invertible (no subtraction). Use 2D sparse table (O(R·C·log R·log C) preprocessing, O(1) query) or 2D segment tree.

Q4: Many updates and queries interleaved on a huge matrix — what structure? A: 2D Fenwick tree if updates are point + queries are range. If both ops are range, four BITs. If R, C are huge but data is sparse, K-D tree variants or implicit segment trees.

Q5: Streaming variant — rows arrive one at a time, query “sum of last K rows × all cols” cheaply. A: Maintain rolling 1D arrays for column sums of last K rows; combine with a 1D prefix sum over columns. Amortized O(C) per row arrival, O(1) per query.

14. Solution Walkthrough

See solution.py:

• NumMatrix(matrix) — preprocesses 2D prefix P with “+1 border.”
• NumMatrix.sumRegion(r1, c1, r2, c2) — O(1) via inclusion-exclusion.
• NumMatrix.sumRegion_brute(r1, c1, r2, c2) — O(area) double loop for oracle.
• stress_test() — 200 random matrices and 50 random queries each, prefix vs brute.
• edge_cases() — 1×1, single row, single col, full matrix, negative values, LC canonical.

Run: python3 solution.py.

15. Beyond the Problem

Principal-engineer code review comment:

“The ‘immutable’ contract here is API-level, not language-level. In Python, callers can still mutate the input matrix they passed to __init__ AFTER construction — our P becomes stale silently. Either deep-copy in __init__ (memory cost) or document loudly that the caller must NOT mutate post-construction. Don’t be smug about ‘immutable in the name’ — your users will not read the spec. For C++ this would be const& and the compiler catches it; in Python it’s discipline. Second: if the matrix is sparse (mostly zeros), this O(R·C) memory is wasteful — consider a dict-of-dict representation or compressed sparse row. Third: the inclusion-exclusion needs a unit test that hand-computes a 2×2 example — every code reviewer doubts the signs. Make the test impossible to misread.”

Connections forward:

• p31 — Subarray Sum K: 1D prefix sum, the predecessor.
• LC 308 — Range Sum Query 2D Mutable: Fenwick tree generalization.
• LC 1314 — Matrix Block Sum: direct application — compute block-window sum for every cell.
• LC 363 — Max Sum of Rectangle No Larger Than K: 2D prefix + binary search via SortedList.
• LC 1074 — Number of Submatrices Sum K: 2D prefix + 1D Subarray Sum K reduction.
• Phase 02 Lab 03 — Prefix Sums: template lab.
• Production: integral images in computer vision (Viola-Jones, OpenCV), summed-area tables in graphics, billing aggregations, financial dashboard cumulative views.