# Solving Leetcode Interviews in Seconds with AI: Range Sum Query 2D - Immutable


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "304" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# 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 its upper left corner (row1, col1) and lower right corner (row2, col2).  You must design an algorithm where sumRegion works on O(1) time complexity.   Example 1:   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]  Explanation NumMatrix numMatrix = new NumMatrix([[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]]); numMatrix.sumRegion(2, 1, 4, 3); // return 8 (i.e sum of the red rectangle) numMatrix.sumRegion(1, 1, 2, 2); // return 11 (i.e sum of the green rectangle) numMatrix.sumRegion(1, 2, 2, 4); // return 12 (i.e sum of the blue rectangle)    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.  

	# Explanation
	Here's the breakdown of the solution:

*   **Prefix Sum Matrix:** The core idea is to precompute a 2D prefix sum matrix. Each cell `prefix_sum[i][j]` stores the sum of all elements in the original `matrix` from `matrix[0][0]` to `matrix[i][j]`.

*   **O(1) Sum Region Calculation:** Using the prefix sum matrix, we can calculate the sum of any rectangular region in O(1) time. The sum of the region defined by `(row1, col1)` and `(row2, col2)` is calculated as `prefix_sum[row2][col2] - prefix_sum[row1-1][col2] - prefix_sum[row2][col1-1] + prefix_sum[row1-1][col1-1]`. We need to handle the edge cases where `row1` or `col1` is 0.

*   **Space-Time Tradeoff:** We trade space for time. We use extra space to store the prefix sum matrix, allowing for very fast (O(1)) query times.

*   **Runtime Complexity:** Initialization: O(m * n), sumRegion: O(1)
    **Storage Complexity:** O(m * n)

	
	# Code
	```python
	class NumMatrix:

    def __init__(self, matrix):
        self.matrix = matrix
        rows = len(matrix)
        cols = len(matrix[0]) if rows > 0 else 0

        self.prefix_sum = [[0] * (cols + 1) for _ in range(rows + 1)]

        for i in range(1, rows + 1):
            for j in range(1, cols + 1):
                self.prefix_sum[i][j] = (
                    self.prefix_sum[i - 1][j] +
                    self.prefix_sum[i][j - 1] -
                    self.prefix_sum[i - 1][j - 1] +
                    matrix[i - 1][j - 1]
                )

    def sumRegion(self, row1, col1, row2, col2):
        row1 += 1
        col1 += 1
        row2 += 1
        col2 += 1

        return (
            self.prefix_sum[row2][col2] -
            self.prefix_sum[row1 - 1][col2] -
            self.prefix_sum[row2][col1 - 1] +
            self.prefix_sum[row1 - 1][col1 - 1]
        )
	```