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, 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

    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]
        )