LeetCode 1314. Matrix Block Sum

Description

https://leetcode.com/problems/matrix-block-sum/

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

Implement as the problem describes.

Python Solution

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
        
        results = []
        for i in range(len(mat)):            
            results.append([])
            for j in range(len(mat[0])):
                results[i].append([None])
        
        for i in range(len(mat)):            
            for j in range(len(mat[0])):                
                value_sum = 0           
                
                for m in range(max(i - k, 0), min(i + k + 1, len(mat))):            
                    for n in range(max(j - k, 0), min(j + k + 1, len(mat[0]))):    
                        
                        value_sum += mat[m][n]

                results[i][j] = value_sum
                
                
        return results
  • Time Complexity: O(N^4).
  • Space Complexity: O(N^2).

Leave a Reply

Your email address will not be published.