LeetCode 304: Range Sum Query 2D - Immutable Solution in Python – A Step-by-Step Guide

What Is LeetCode 304: Range Sum Query 2D - Immutable?

In LeetCode 304: Range Sum Query 2D - Immutable, you’re tasked with creating a NumMatrix class with two methods: __init__(matrix) to set up an immutable 2D integer matrix, and sumRegion(row1, col1, row2, col2) to return the sum of elements within the rectangle defined by top-left (row1, col1) and bottom-right (row2, col2). The matrix is fixed, but sumRegion will be called many times. For example, with a matrix [[3, 0, 1], [5, 6, 3]], sumRegion(0, 0, 1, 1) returns 3 + 0 + 5 + 6 = 14. This problem tests your ability to preprocess 2D data for quick queries, building on LeetCode 303: Range Sum Query - Immutable.

Problem Statement

• Input: A 2D integer array matrix for __init__; integers row1, col1, row2, col2 for sumRegion.
• Output: A class with:
• __init__(matrix): Initializes with matrix (returns nothing).
• sumRegion(row1, col1, row2, col2): Returns sum of rectangle.
• Rules: Matrix is immutable; sumRegion called multiple times; indices are valid.

Constraints

• Matrix size: m x n, where 1 ≤ m, n ≤ 200.
• Values: -10⁵ to 10⁵.
• row1 ≤ row2, col1 ≤ col2, all within bounds.
• Up to 10⁴ sumRegion calls.

Examples

• Input: ["NumMatrix","sumRegion","sumRegion","sumRegion"], [[[[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]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
• Output: [null, 8, 11, 12]
• Input: ["NumMatrix","sumRegion"], [[[[1,2]], [0,1]]], [0,0,1,1]]
• Output: [null, 4] (1+2+0+1=4)
• Input: ["NumMatrix","sumRegion"], [[[[5]]], [0,0,0,0]]
• Output: [null, 5]

Understanding the Problem: Summing 2D Ranges Fast

To solve LeetCode 304: Range Sum Query 2D - Immutable in Python, we need a class that takes a 2D matrix once and then quickly sums any rectangular region from (row1, col1) to (row2, col2). For [[3, 0], [5, 6]], sumRegion(0, 0, 1, 1) is 3 + 0 + 5 + 6 = 14, and we’ll face many such calls. Adding numbers each time would work but be slow with frequent queries. Instead, we’ll use:

• Best Solution (2D Prefix Sum Array): O(m*n) init, O(1) sumRegion, O(m*n) space—fast and efficient.
• Alternative Solution (Brute Force Summation): O(1) init, O(m*n) sumRegion, O(m*n) space—simple but slow.

Let’s dive into the 2D prefix sum solution with a friendly breakdown that’s easy to follow.

Best Solution: 2D Prefix Sum Array

Why This Is the Best Solution

The 2D prefix sum array is the top choice for LeetCode 304 because it’s highly efficient—O(mn) time to set up during __init__, O(1) time for each sumRegion call, and O(mn) space. It precomputes cumulative sums for all rectangles from (0,0) to every (i,j), so any range sum is just a few subtractions. It’s like having a pre-made sum map for the whole grid—ideal for tons of queries!

How It Works

Let’s picture this like a growing sum grid:

• Step 1: Build 2D Prefix Sums:
• Create a matrix prefix where prefix[i][j] = sum of all elements from (0,0) to (i-1,j-1).
• For each (i,j): prefix[i][j] = matrix[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] (avoid double-counting).
• Add padding (extra row/col of 0s) for easier math.
• Step 2: Compute Range Sum:
• Sum from (row1, col1) to (row2, col2) = prefix[row2+1][col2+1] - prefix[row2+1][col1] - prefix[row1][col2+1] + prefix[row1][col1].
• Subtracts areas outside the target rectangle, adjusts for overlap.
• Step 3: Why It Works:
• Prefix sums cover all sub-rectangles from origin.
• Inclusion-exclusion principle isolates the exact region.
• O(1) lookup beats summing each time.

It’s like a 2D sum cheat sheet—subtract and conquer!

Step-by-Step Example

Example: matrix = [[3,0,1],[5,6,3]]

• Init:
• Prefix = [[0,0,0,0], [0,3,3,4], [0,8,14,18]]:
• [0,0,0,0] (padding).
• [0,3,3+0,3+0+1] = [0,3,3,4].
• [0,8,8+6,8+6+3] = [0,8,14,18] (add prev row).
• sumRegion(0, 0, 1, 1):
• prefix[2][2] - prefix[2][0] - prefix[0][2] + prefix[0][0] = 14 - 0 - 0 + 0 = 14 (3+0+5+6).
• sumRegion(1, 0, 1, 2):
• prefix[2][3] - prefix[2][0] - prefix[1][3] - prefix[1][0] = 18 - 0 - 4 + 0 = 14 (5+6+3).
• sumRegion(0, 1, 0, 1):
• prefix[1][2] - prefix[1][1] - prefix[0][2] + prefix[0][1] = 3 - 3 - 0 + 0 = 0 (0).
• Result: Fast every time!

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so it’s easy to follow:

Copy codeclass NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        # Step 1: Get matrix size and build prefix sum array
        m, n = len(matrix), len(matrix[0])
        self.prefix = [[0] * (n + 1) for _ in range(m + 1)]  # Padding

        # Fill prefix sums
        for i in range(m):
            for j in range(n):
                self.prefix[i + 1][j + 1] = (matrix[i][j] + 
                                              self.prefix[i + 1][j] + 
                                              self.prefix[i][j + 1] - 
                                              self.prefix[i][j])

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        # Step 2: Compute range sum with inclusion-exclusion
        return (self.prefix[row2 + 1][col2 + 1] - 
                self.prefix[row2 + 1][col1] - 
                self.prefix[row1][col2 + 1] + 
                self.prefix[row1][col1])

• Line 4-6: In __init__:
• Get dimensions m, n.
• Create prefix array with padding (m+1 x n+1), all 0s.
• Line 9-12: Fill prefix:
• prefix[i+1][j+1] = matrix[i][j] + left + above - overlap (inclusion-exclusion).
• Line 15-18: In sumRegion:
• Return prefix[bottom+1][right+1] - left edge - top edge + overlap corner.
• Time Complexity: O(m*n) init, O(1) sumRegion.
• Space Complexity: O(m*n)—prefix array.

This is like a 2D sum map—subtract and get it!

Alternative Solution: Brute Force Summation

Why an Alternative Approach?

Brute force summation stores the matrix as-is—O(1) init, O(mn) sumRegion, O(mn) space. It’s simpler but slower, adding numbers each time sumRegion is called, like summing a grid on the spot—great for learning but not for speed with many queries.

How It Works

Let’s think of this as a manual count:

• Step 1: Store the matrix in __init__.
• Step 2: For sumRegion, loop over rows from row1 to row2 and cols from col1 to col2, adding each number.
• Step 3: Return the sum.

It’s like tallying a rectangle cell-by-cell each time!

Step-by-Step Example

Example: matrix = [[3,0],[5,6]]

• Init: matrix = [[3,0],[5,6]].
• sumRegion(0, 0, 1, 1):
• 3 + 0 + 5 + 6 = 14.
• sumRegion(1, 0, 1, 0):
• 5 = 5.
• Result: Works, but slow with many calls.

Code for Brute Force Approach

Copy codeclass NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        self.matrix = matrix  # Just store the matrix

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        total = 0
        for i in range(row1, row2 + 1):  # Loop over rows
            for j in range(col1, col2 + 1):  # Loop over cols
                total += self.matrix[i][j]
        return total

• Time Complexity: O(1) init, O(m*n) sumRegion.
• Space Complexity: O(m*n)—stores matrix.

It’s a slow tally each time!

Comparing the Two Solutions

• 2D Prefix Sum (Best):
• Pros: O(m*n) init, O(1) sumRegion, O(m*n) space, fast queries.
• Cons: Precomputation effort.
• Brute Force (Alternative):
• Pros: O(1) init, O(m*n) sumRegion, O(m*n) space, simple setup.
• Cons: Slow queries.

Prefix sum wins for many calls.

Additional Examples and Edge Cases

• [[1]], (0,0,0,0): 1.
• [[1,2],[3,4]], (0,0,1,1): 10.
• [[-1,1]], (0,0,0,1): 0.

Prefix sum is faster.

Complexity Breakdown

• Prefix Sum: Init O(m*n), SumRegion O(1), Space O(m*n).
• Brute Force: Init O(1), SumRegion O(m*n), Space O(m*n).

Prefix sum rules.

Key Takeaways

• Prefix Sum: Precompute for speed—smart!
• Brute Force: Add on demand—clear!
• 2D: Grids love sums.
• Python Tip: Arrays rock—see [Python Basics](/python/basics).

Final Thoughts: Sum That Grid

LeetCode 304: Range Sum Query 2D - Immutable in Python is a slick 2D challenge. 2D prefix sums zip through queries, while brute force shows the basics. Want more? Try LeetCode 303: Range Sum Query - Immutable or LeetCode 560: Subarray Sum Equals K. Ready to tally? Head to Solve LeetCode 304 on LeetCode and sum those ranges today!