# Solving Leetcode Interviews in Seconds with AI: Matrix Block Sum


	# 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](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 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
	```python
	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
	```