Problem Description

You are given a 2D matrix of integers and need to efficiently calculate the sum of elements within any rectangular region of this matrix.

The task requires implementing a NumMatrix class with two methods:

1. Constructor NumMatrix(int[][] matrix): Takes a 2D integer matrix as input and initializes the data structure.

2. Query Method sumRegion(int row1, int col1, int row2, int col2): Returns the sum of all elements within the rectangle defined by:

   • Upper left corner at position (row1, col1)
   • Lower right corner at position (row2, col2)
   • Both corners are inclusive in the sum calculation

Key Constraint: The sumRegion method must operate in O(1) time complexity, meaning each query should return the result in constant time regardless of the rectangle size.

The solution uses a 2D prefix sum approach. A prefix sum array s[i+1][j+1] stores the sum of all elements from the top-left corner (0, 0) to position (i, j) in the original matrix.

During initialization, the prefix sum array is built using the formula: s[i+1][j+1] = s[i][j+1] + s[i+1][j] - s[i][j] + matrix[i][j]

For any query, the sum of a rectangle can be calculated in constant time using: sum = s[row2+1][col2+1] - s[row2+1][col1] - s[row1][col2+1] + s[row1][col1]

This formula works by taking the total sum up to the bottom-right corner, then subtracting the regions outside the desired rectangle (left and top portions), and adding back the overlapping corner that was subtracted twice.

Intuition

The naive approach would be to iterate through all elements in the rectangle for each query, but this would take O(m*n) time per query where m and n are the dimensions of the rectangle. Since we need O(1) query time, we need to do some preprocessing.

Think about how we handle range sum queries in a 1D array - we use prefix sums where prefix[i] stores the sum of elements from index 0 to i. Then any range sum from index i to j can be calculated as prefix[j] - prefix[i-1] in constant time.

Can we extend this idea to 2D? Yes! We can create a 2D prefix sum where each cell stores the sum of all elements in the rectangle from (0,0) to that cell.

To visualize this, imagine you want the sum of a rectangle. If you have the sum of the entire region from origin to the bottom-right corner of your target rectangle, you've included too much. You need to subtract the regions to the left and above your target rectangle. But wait - when you subtract both these regions, you've subtracted their overlap twice! So you need to add it back once.

This gives us the inclusion-exclusion principle for 2D:

• Start with the sum from origin to bottom-right: s[row2+1][col2+1]
• Subtract the left excess: - s[row2+1][col1]
• Subtract the top excess: - s[row1][col2+1]
• Add back the overlap: + s[row1][col1]

Building the prefix sum array follows similar logic. To calculate the sum up to position (i,j), we take the sum up to (i-1,j) and (i,j-1), subtract their overlap (i-1,j-1) (which was counted twice), and add the current element matrix[i][j].

This preprocessing takes O(m*n) time once, but then every query is just four array lookups - achieving our O(1) goal.

Solution Approach

The solution implements a 2D prefix sum array to achieve constant-time rectangle sum queries.

Data Structure:

• Create a 2D array s with dimensions (m+1) x (n+1) where m and n are the rows and columns of the original matrix
• The extra row and column (filled with zeros) simplify boundary handling by eliminating the need for special cases

Initialization Phase:

During construction, we build the prefix sum array where s[i+1][j+1] represents the sum of all elements in the rectangle from (0,0) to (i,j) in the original matrix.

For each cell, we calculate:

s[i+1][j+1] = s[i][j+1] + s[i+1][j] - s[i][j] + matrix[i][j]

Breaking down this formula:

• s[i][j+1]: sum of rectangle from (0,0) to (i-1,j)
• s[i+1][j]: sum of rectangle from (0,0) to (i,j-1)
• s[i][j]: sum of rectangle from (0,0) to (i-1,j-1) (subtracted because it's counted twice)
• matrix[i][j]: current element value

Query Phase:

To find the sum of rectangle from (row1, col1) to (row2, col2), we use:

sum = s[row2+1][col2+1] - s[row2+1][col1] - s[row1][col2+1] + s[row1][col1]

This applies the inclusion-exclusion principle:

1. s[row2+1][col2+1]: total sum from origin to (row2, col2)
2. -s[row2+1][col1]: subtract the left region outside our target rectangle
3. -s[row1][col2+1]: subtract the top region outside our target rectangle
4. +s[row1][col1]: add back the top-left region that was subtracted twice

Time Complexity:

• Initialization: O(m*n) to build the prefix sum array
• Query: O(1) as it only involves four array lookups and arithmetic operations

Space Complexity: O(m*n) for storing the prefix sum array

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Given matrix:

[3, 0, 1]
[5, 6, 3]
[1, 2, 0]

Step 1: Build the Prefix Sum Array

We create a prefix sum array s with dimensions (4 x 4) - one row and column larger than the original matrix. The first row and column are initialized with zeros.

Starting with:

s = [0, 0, 0, 0]
    [0, ?, ?, ?]
    [0, ?, ?, ?]
    [0, ?, ?, ?]

Now we fill each cell using the formula: s[i+1][j+1] = s[i][j+1] + s[i+1][j] - s[i][j] + matrix[i][j]

For position (0,0) in matrix (value = 3):

• s[1][1] = s[0][1] + s[1][0] - s[0][0] + 3 = 0 + 0 - 0 + 3 = 3

For position (0,1) in matrix (value = 0):

• s[1][2] = s[0][2] + s[1][1] - s[0][1] + 0 = 0 + 3 - 0 + 0 = 3

For position (0,2) in matrix (value = 1):

• s[1][3] = s[0][3] + s[1][2] - s[0][2] + 1 = 0 + 3 - 0 + 1 = 4

Continuing this process for all cells, we get:

s = [0, 0, 0, 0]
    [0, 3, 3, 4]
    [0, 8, 14, 18]
    [0, 9, 17, 21]

Each cell s[i][j] contains the sum of all elements from (0,0) to (i-1,j-1) in the original matrix.

Step 2: Query Example - Sum of Rectangle from (1,1) to (2,2)

We want to find the sum of:

[6, 3]
[2, 0]

Using our formula: sum = s[row2+1][col2+1] - s[row2+1][col1] - s[row1][col2+1] + s[row1][col1]

Substituting values:

• row1 = 1, col1 = 1, row2 = 2, col2 = 2
• sum = s[3][3] - s[3][1] - s[1][3] + s[1][1]
• sum = 21 - 9 - 4 + 3
• sum = 11

Let's verify: 6 + 3 + 2 + 0 = 11 ✓

Visual Understanding:

The calculation works because:

• s[3][3] = 21 gives us everything from (0,0) to (2,2)
• We subtract s[3][1] = 9 to remove the left column (values 3, 5, 1)
• We subtract s[1][3] = 4 to remove the top row (values 3, 0, 1)
• We add back s[1][1] = 3 because we subtracted the top-left corner (value 3) twice

This demonstrates how the 2D prefix sum enables constant-time rectangle sum queries after the initial preprocessing.

Solution Implementation

Time and Space Complexity

Time Complexity:

• Initialization (__init__): O(m × n), where m is the number of rows and n is the number of columns in the input matrix. The algorithm iterates through each element of the matrix exactly once to build the 2D prefix sum array. Each cell computation involves constant time operations (addition and subtraction).

• Query (sumRegion): O(1). The method performs exactly four array lookups and three arithmetic operations (two subtractions and one addition), all of which take constant time regardless of the size of the queried region.

Space Complexity:

• O(m × n). The algorithm creates a 2D prefix sum array self.s with dimensions (m + 1) × (n + 1) to store the cumulative sums. This auxiliary array requires space proportional to the size of the input matrix. The extra row and column (the +1 in dimensions) are used as padding to simplify boundary conditions but don't change the overall space complexity class.

The prefix sum approach trades additional space for efficient query performance, making it ideal for scenarios with multiple range sum queries on the same matrix.

Common Pitfalls

1. Off-by-One Errors in Index Mapping

The most common mistake is confusion between the original matrix indices and the prefix sum array indices. Since the prefix sum array has an extra row and column (padding with zeros), there's a shift in indexing:

• prefix_sum[i+1][j+1] corresponds to the sum from (0,0) to (i,j) in the original matrix
• Many developers accidentally use prefix_sum[i][j] for position (i,j), leading to incorrect results

Solution: Always remember the +1 offset when accessing the prefix sum array. Think of prefix_sum[i][j] as "the sum up to but not including row i and column j."

2. Incorrect Formula Application During Initialization

When building the prefix sum, developers often write:

# WRONG - Missing the overlap subtraction
self.prefix_sum[i+1][j+1] = (
    self.prefix_sum[i][j+1] + 
    self.prefix_sum[i+1][j] + 
    matrix[i][j]
)

This double-counts the rectangle from (0,0) to (i-1,j-1), resulting in inflated sums.

Solution: Always subtract the overlap: - self.prefix_sum[i][j]

3. Forgetting to Handle Empty Matrix Edge Cases

If not careful with initialization, the code might crash on empty matrices or matrices with zero rows/columns:

# This would fail if matrix is empty
rows, cols = len(matrix), len(matrix[0])  # IndexError if matrix is []

Solution: Add validation at the beginning:

if not matrix or not matrix[0]:
    self.prefix_sum = [[0]]
    return

4. Incorrect Rectangle Sum Formula Signs

A frequent error is mixing up the signs in the query formula:

# WRONG - Incorrect signs
return (
    self.prefix_sum[row2 + 1][col2 + 1] +  # Should be +
    self.prefix_sum[row2 + 1][col1] -      # Should be -
    self.prefix_sum[row1][col2 + 1] -      # Should be -
    self.prefix_sum[row1][col1]            # Should be +
)

Solution: Remember the pattern: main rectangle (+), subtract left (-), subtract top (-), add back overlap (+). Visualizing the rectangles being added/subtracted helps prevent sign errors.

5. Not Understanding Why the Extra Row/Column is Needed

Some developers try to optimize by removing the padding:

# WRONG - Creates complex boundary conditions
self.prefix_sum = [[0] * cols for _ in range(rows)]

This requires special handling when row1 = 0 or col1 = 0, making the code error-prone.

Solution: Keep the padding. The small space overhead eliminates all boundary condition checks, making the code cleaner and less bug-prone.