#1292

Maximum Side Length of a Square with Sum Less than or Equal to Threshold

specialist · 635 · lc medium +30 · verified · 65.4% accepted · 1,539 likes · top 70%

Description

In a m x n matrix mat, find the largest side length of any square submatrix whose element sum does not exceed threshold. If no such square exists, return 0.

Example 1:

Input: mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4

Output: 2

Explanation: The maximum side length of square with sum less than or equal to 4 is 2 as shown.

Example 2:

Input: mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1

Output: 0

Code

1

2

3

class Solution:
    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:

class Solution:
    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int: