What is the approach for solving 'Maximum Side Length of a Square with Sum Less than or Equal to Threshold'?

The approach involves using binary search over possible square sizes and a prefix sum array to quickly check the sum of elements in each square.

How do I efficiently check sums of squares in the matrix?

Use a prefix sum array to quickly calculate the sum of any submatrix in constant time, avoiding recalculating sums repeatedly.

What is the role of binary search in this problem?

Binary search is used to explore possible side lengths of the square, narrowing down the maximum valid side length.

How does the sliding window technique help in this problem?

The sliding window technique, in combination with the prefix sum array, allows efficient checking of the sum of elements in multiple possible squares of the same size.

What are the time and space complexities of the solution?

The time complexity is O(log(min(m, n)) * m * n), and the space complexity is O(m * n) due to the prefix sum array.

#1292

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

元素和小于等于阈值的正方形的最大边长

给你一个大小为 m x n 的矩阵 mat 和一个整数阈值 threshold 。请你返回元素总和小于或等于阈值的正方形区域的最大边长；如果没有这样的正方形区域，则返回 0 。示例 1：输入： mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,…

数组二分查找矩阵前缀和

题目描述

给你一个大小为 m x n 的矩阵 mat 和一个整数阈值 threshold。

请你返回元素总和小于或等于阈值的正方形区域的最大边长；如果没有这样的正方形区域，则返回 0 。

示例 1：

输入：mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4
输出：2
解释：总和小于或等于 4 的正方形的最大边长为 2，如图所示。

示例 2：

输入：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
输出：0

提示：

m == mat.length
n == mat[i].length
1 <= m, n <= 300
0 <= mat[i][j] <= 10⁴
0 <= threshold <= 10⁵

lightbulb

解题思路

方法一：二维前缀和 + 二分查找

我们可以先预处理得到二维前缀和数组 $s$ ，其中 $s[i + 1][j + 1]$ 表示矩阵 $mat$ 中从 $(0, 0)$ 到 $(i, j)$ 的元素和，那么对于任意的正方形区域，我们都可以在 $O(1)$ 的时间内得到其元素和。

接下来，我们可以使用二分查找的方法得到最大的边长。我们枚举正方形的边长 $k$ ，然后枚举正方形的左上角位置 $(i, j)$ ，那么我们可以得到正方形的元素和 $v$ ，如果 $v \leq threshold$ ，那么说明存在边长为 $k$ 的正方形区域的元素和小于或等于阈值，否则不存在。

时间复杂度 $O(m \times n \times \log \min(m, n))$ ，空间复杂度 $O(m \times n)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

class Solution:
    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
        def check(k: int) -> bool:
            for i in range(m - k + 1):
                for j in range(n - k + 1):
                    v = s[i + k][j + k] - s[i][j + k] - s[i + k][j] + s[i][j]
                    if v <= threshold:
                        return True
            return False

        m, n = len(mat), len(mat[0])
        s = [[0] * (n + 1) for _ in range(m + 1)]
        for i, row in enumerate(mat, 1):
            for j, x in enumerate(row, 1):
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x
        l, r = 0, min(m, n)
        while l < r:
            mid = (l + r + 1) >> 1
            if check(mid):
                l = mid
            else:
                r = mid - 1
        return l

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Tests the candidate's understanding of binary search in a 2D matrix context.
question_mark
Evaluates how the candidate uses optimization techniques like prefix sums and sliding window.
question_mark
Assesses problem-solving skills under constraints with a focus on space-time trade-offs.

warning

常见陷阱

外企场景

error
Failing to optimize sum calculation by not using a prefix sum array.
error
Not correctly implementing binary search over the possible side lengths, which could lead to inefficient solutions.
error
Misunderstanding the use of sliding window in conjunction with the prefix sum array.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modifying the threshold value to test performance with different limits.
arrow_right_alt
Using different matrix configurations like sparse or fully populated matrices.
arrow_right_alt
Adding constraints on the number range of matrix elements or threshold.

help

常见问题

外企场景

继续练习

#363 矩形区域不超过 K 的最大数值和 #1444 切披萨的方案数 #1508 子数组和排序后的区间和