Introduction

In this blog post, we will explore how to solve the LeetCode problem "1314" 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 m x n matrix mat and an integer k, return a matrix answer where each answer[i][j] is the sum of all elements mat[r][c] for: i - k <= r <= i + k, j - k <= c <= j + k, and (r, c) is a valid position in the matrix. Example 1: Input: mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1 Output: [[12,21,16],[27,45,33],[24,39,28]] Example 2: Input: mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2 Output: [[45,45,45],[45,45,45],[45,45,45]] Constraints: m == mat.length n == mat[i].length 1 <= m, n, k <= 100 1 <= mat[i][j] <= 100

Explanation

Here's a breakdown of the optimal solution:

• Prefix Sum: The core idea is to precompute a 2D prefix sum matrix. This allows us to calculate the sum of any submatrix in O(1) time.
• Submatrix Sum Calculation: For each cell (i, j) in the output matrix, we use the prefix sum matrix to find the sum of the elements within the defined window [i-k:i+k, j-k:j+k].

• Boundary Handling: We carefully handle boundary conditions to ensure that we only sum elements within the valid matrix indices.

• Runtime Complexity: O(m*n) , Storage Complexity: O(m*n)

Code

    def matrixBlockSum(mat, k):
    m, n = len(mat), len(mat[0])
    prefix_sum = [[0] * (n + 1) for _ in range(m + 1)]

    # Calculate prefix sum matrix
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            prefix_sum[i][j] = mat[i-1][j-1] + prefix_sum[i-1][j] + prefix_sum[i][j-1] - prefix_sum[i-1][j-1]

    answer = [[0] * n for _ in range(m)]

    # Calculate block sums using prefix sum
    for i in range(m):
        for j in range(n):
            row_start = max(0, i - k)
            row_end = min(m - 1, i + k)
            col_start = max(0, j - k)
            col_end = min(n - 1, j + k)

            answer[i][j] = prefix_sum[row_end + 1][col_end + 1] - prefix_sum[row_start][col_end + 1] - prefix_sum[row_end + 1][col_start] + prefix_sum[row_start][col_start]

    return answer