shuuji3.xyz
[READ-ONLY] Mirror of https://github.com/shuuji3/leetcode. 馃搩 Code submitted to LeetCode
leetcode.com/shuuji3/
leetcode
leetcode-solutions
leetcode
/
weekly-contest-167
/
1292.maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold.286043444.notac.py
2.2 kB
84 lines
1#
2# @lc app=leetcode id=1292 lang=python3
3#
4# [1292] Maximum Side Length of a Square with Sum Less than or Equal to Threshold
5#
6# https://leetcode.com/problems/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold/description/
7#
8# algorithms
9# Medium (39.22%)
10# Total Accepted: 2.9K
11# Total Submissions: 7.3K
12# Testcase Example: '[[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]]\n4'
13#
14# Given a m x n聽matrix mat and an integer threshold. Return the maximum
15# side-length of a square with a sum less than or equal to threshold or return
16# 0 if there is no such square.
17#
18#
19# Example 1:
20#
21#
22# 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
23# Output: 2
24# Explanation: The maximum side length of square with sum less than 4 is 2 as
25# shown.
26#
27#
28# Example 2:
29#
30#
31# 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]],
32# threshold = 1
33# Output: 0
34#
35#
36# Example 3:
37#
38#
39# Input: mat = [[1,1,1,1],[1,0,0,0],[1,0,0,0],[1,0,0,0]], threshold = 6
40# Output: 3
41#
42#
43# Example 4:
44#
45#
46# Input: mat = [[18,70],[61,1],[25,85],[14,40],[11,96],[97,96],[63,45]],
47# threshold = 40184
48# Output: 2
49#
50#
51#
52# Constraints:
53#
54#
55# 1 <= m, n <= 300
56# m == mat.length
57# n == mat[i].length
58# 0 <= mat[i][j] <= 10000
59# 0 <= threshold聽<= 10^5
60#
61#
62class Solution:
63 def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
64 rows, cols = len(mat), len(mat[0])
65 max_size = max(rows, cols)
66 max_side_length = 0
67
68 for i in reversed(range(max_size)):
69 size = i+1
70 for start_row in range(rows):
71 if start_row + size > rows:
72 break
73 for start_col in range(cols):
74 if start_col + size > cols:
75 break
76 sum_of_square = 0
77 for row in range(size):
78 mat_row = mat[start_row + row]
79 for col in range(size):
80 sum_of_square += mat_row[start_col + col]
81 if sum_of_square <= threshold:
82 return size
83 return 0
84