Log inSign up
mediumLeetCodeNot Started

Range Sum Query 2D - Immutable

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

Given a 2D matrix matrix, handle multiple queries of the following type: - Calculate the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Implement the NumMatrix class: - NumMatrix(int[][] matrix) Initializes the object with the integer matrix matrix. - int sumRegion(int row1, int col1, int row2, int col2) Returns the sum of the elements of matrix inside the rectangle defined by upper left corner (row1, col1) and lower right corner (row2, col2).

Example 1 · Standard 2D Matrix Query:

Input: 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]], query = (2, 1, 4, 3)
Output: 8
Explanation: Sum of rectangular subgrid from (2,1) to (4,3) is 2+0+1 + 1+0+1 + 0+3+0 = 8.

Example 2 · Single Cell Region:

Input: matrix = [[1, 2], [3, 4]], query = (1, 1, 1, 1)
Output: 4
Explanation: Query on single cell (1, 1) returns 4.

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 200
  • -104 <= matrix[i][j] <= 104
  • 0 <= row1 <= row2 < m
  • 0 <= col1 <= col2 < n
  • At most 104 calls will be made to sumRegion.

Prerequisites

Before attempting this problem, you should be comfortable with:

  • 1D Prefix Sum concept
  • 2D Grid indexing and geometry
  • Inclusion-Exclusion principle

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the 2D Inclusion-Exclusion formula for prefix sums.
  • Utilize 1-indexed padding to eliminate boundary checks.
  • Design O(1) subgrid query systems for immutable grids.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • If the array is sorted or can be sorted without violating problem requirements, evaluate Two Pointers or Binary Search.
  • If tracking contiguous subsegments with monotone expansion/shrinkage, apply Sliding Window.
  • If frequency or complement lookups are required in O(1) time, use a Hash Map or Frequency Array.

Connected Patterns:

Range Sum Query - Immutable (1D)Maximal Rectangle / 2D Prefix Sums

1. Direct 2D Iteration (Brute Force)

Intuition

Given rectangle bounds (row1, col1) to (row2, col2), execute two nested loops summing matrix[r][c] for row1 <= r <= row2 and col1 <= c <= col2. Each query takes O((row2 - row1 + 1) * (col2 - col1 + 1)).

When to apply: Use for one-off single queries when matrix memory cannot be allocated for preprocessing.

Nested Matrix Cells Iteration (O(R * C) per Query)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Directly reading cell (1, 1)
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
c3
c4
c5
c6
c7
c8
r0
3
0
1
5
6
↑ cell
3
1
2
0
Variables at this step
r
1
c
1
cellVal
6
currentSum
6
Check / comparison
Visit first queried cell (r=1, c=1): matrix[1][1] = 6
Decision / next transition
Initialize sum = 6.
Why this step matters

Directly reading cell (1, 1).

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class NumMatrix {
3 private int[][] mat;
4
5 public NumMatrix(int[][] matrix) {
6 this.mat = matrix;
7 }
8
9 public int sumRegion(int row1, int col1, int row2, int col2) {
10 int sum = 0;
11 for (int r = row1; r <= row2; r++) {
12 for (int c = col1; c <= col2; c++) {
13 sum += mat[r][c];
14 }
15 }
16 return sum;
17 }
18 }
19
20 public static void main(String[] args) {
21 int[][] matrix = {
22 {3, 0, 1, 4, 2},
23 {5, 6, 3, 2, 1},
24 {1, 2, 0, 1, 5},
25 {4, 1, 0, 1, 7},
26 {1, 0, 3, 0, 5}
27 };
28 NumMatrix nm = new NumMatrix(matrix);
29 System.out.println("Region Sum: " + nm.sumRegion(2, 1, 4, 3));
30 }
31}

Time & Space Complexity

  • Time complexity: O(1) init, O(R * C) per query — No precomputation; each query iterates through the queried rectangle of size R * C.
  • Space complexity: O(1) — Only constant extra accumulator variables.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Row-Wise 1D Prefix Sums (Better)

Intuition

For each row r, compute prefix sums rowPrefix[r][c] = sum(matrix[r][0..c-1]). Then in sumRegion, iterate over each row from row1 to row2 and add rowPrefix[r][col2+1] - rowPrefix[r][col1]. Each query takes O(R) time.

When to apply: Use when 2D prefix table algebra is not needed and row-wise streaming is preferred.

Row-Wise 1D Prefix Sums (O(Rows) per Query)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Replaces inner column loop with constant time subtraction
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
c3
c4
c5
c6
c7
c8
c9
c10
c11
r0
0
↑ rowPrefix
3
3
4
0
5
11
14
0
1
3
3
Variables at this step
rowPrefixBuilt
true
currentSum
0
Check / comparison
Build 1D prefix sums for each row: Row 1 is [0, 5, 11, 14], Row 2 is [0, 1, 3, 3]
Decision / next transition
Each row's slice sum [col1..col2] is rowPref[col2+1] - rowPref[col1].
Why this step matters

Replaces inner column loop with constant time subtraction.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class NumMatrix {
3 private int[][] rowPrefix;
4
5 public NumMatrix(int[][] matrix) {
6 int m = matrix.length, n = matrix[0].length;
7 rowPrefix = new int[m][n + 1];
8 for (int r = 0; r < m; r++) {
9 for (int c = 0; c < n; c++) {
10 rowPrefix[r][c + 1] = rowPrefix[r][c] + matrix[r][c];
11 }
12 }
13 }
14
15 public int sumRegion(int row1, int col1, int row2, int col2) {
16 int sum = 0;
17 for (int r = row1; r <= row2; r++) {
18 sum += rowPrefix[r][col2 + 1] - rowPrefix[r][col1];
19 }
20 return sum;
21 }
22 }
23
24 public static void main(String[] args) {
25 int[][] matrix = {
26 {3, 0, 1, 4, 2},
27 {5, 6, 3, 2, 1},
28 {1, 2, 0, 1, 5},
29 {4, 1, 0, 1, 7},
30 {1, 0, 3, 0, 5}
31 };
32 NumMatrix nm = new NumMatrix(matrix);
33 System.out.println("Region Sum: " + nm.sumRegion(2, 1, 4, 3));
34 }
35}

Time & Space Complexity

  • Time complexity: O(R * C) init, O(R) per query — Precomputing row prefix sums takes O(R * C). Each query performs row2 - row1 + 1 additions, taking O(R) time.
  • Space complexity: O(R * C) — O(R * C) memory to store the row-wise prefix sums.

3. 2D Integral Image Prefix Sum Table (Optimal)

Intuition

1. Precomputation (O(M*N)): dp[r+1][c+1] = matrix[r][c] + dp[r][c+1] + dp[r+1][c] - dp[r][c]. 2. Query (O(1)): By inclusion-exclusion principle, any rectangle (row1, col1, row2, col2) is calculated as: dp[row2+1][col2+1] - dp[row1][col2+1] - dp[row2+1][col1] + dp[row1][col1].

When to apply: Use as the optimal standard solution whenever answering multiple 2D region queries.

2D Integral Image / Inclusion-Exclusion (O(1) per Query)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Integral image precomputation takes O(R C) time once
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
c3
c4
c5
c6
c7
c8
c9
c10
c11
c12
c13
c14
c15
r0
0
↑ dp2D
0
0
0
0
3
3
4
0
8
14
18
0
9
17
21
Variables at this step
dpSize
4x4
precomputed
true
Check / comparison
Precompute 2D prefix sum table dp of size (R+1) x (C+1)
Decision / next transition
dp[r+1][c+1] = matrix[r][c] + dp[r][c+1] + dp[r+1][c] - dp[r][c].
Why this step matters

Integral image precomputation takes O(R * C) time once.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class NumMatrix {
3 private int[][] dp;
4
5 public NumMatrix(int[][] matrix) {
6 int m = matrix.length, n = matrix[0].length;
7 dp = new int[m + 1][n + 1];
8 for (int r = 0; r < m; r++) {
9 for (int c = 0; c < n; c++) {
10 dp[r + 1][c + 1] = matrix[r][c] + dp[r][c + 1] + dp[r + 1][c] - dp[r][c];
11 }
12 }
13 }
14
15 public int sumRegion(int row1, int col1, int row2, int col2) {
16 return dp[row2 + 1][col2 + 1] - dp[row1][col2 + 1] - dp[row2 + 1][col1] + dp[row1][col1];
17 }
18 }
19
20 public static void main(String[] args) {
21 int[][] matrix = {
22 {3, 0, 1, 4, 2},
23 {5, 6, 3, 2, 1},
24 {1, 2, 0, 1, 5},
25 {4, 1, 0, 1, 7},
26 {1, 0, 3, 0, 5}
27 };
28 NumMatrix nm = new NumMatrix(matrix);
29 System.out.println("Region Sum: " + nm.sumRegion(2, 1, 4, 3));
30 }
31}

Time & Space Complexity

  • Time complexity: O(M * N) init, O(1) per query — Precomputing the 2D prefix table takes O(M * N) time. Each query evaluates 4 lookups in O(1) time.
  • Space complexity: O(M * N) — O(M * N) auxiliary memory for the (M+1) x (N+1) DP prefix table.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Direct IterationO(1) init, O(R * C) per queryO(1) extra spaceLoop through every cell (r, c) from row1 to row2 and col1 to col2.Recomputes cell sums repeatedly.
2.Better — 1D Row-wise Prefix SumsO(R * C) init, O(R) per queryO(R * C)Compute 1D prefix sum for each row. Query sums row-by-row in O(R) time.Iterates through all R rows in the query.
3.Optimal — 2D Prefix Sum (Inclusion-Exclusion)OptimalO(R * C) init, O(1) per queryO(R * C)Build 2D prefix sum table. Answer any rectangle query in exactly 4 table lookups.None; optimal.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Empty or Single Element Array — Handle minimal input sizes (N = 0 or N = 1) cleanly without out-of-bounds errors.
  • Duplicate Elements — Verify behavior when all elements are identical (e.g. all 0s or all equal values).
  • Extreme Numerical Values — Account for maximum/minimum allowed constraint values (-109 to 109) to prevent overflow.
  • Boundary Conditions — Ensure correct execution when target or match is located at the first or last index.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Range Sum Query 2D - Immutable?

2.Why is the brute force approach suboptimal for large inputs in Range Sum Query 2D - Immutable?

3.Which data structure or technique enables the optimal solution for Range Sum Query 2D - Immutable?

Back to DSA Sheet