#1292

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

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

This problem challenges you to find the largest square in a matrix with a sum below a given threshold using binary search and prefix sums.

array binary search matrix prefix sum

Problem Statement

You are given an m x n matrix mat and an integer threshold. Your goal is to return the maximum side length of a square whose sum of elements is less than or equal to the threshold. If no such square exists, return 0.

To solve this problem efficiently, you need to apply binary search over the side lengths of possible squares and use prefix sums to check if the sum of any square's elements exceeds the threshold.

Examples

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

The maximum side length of square with sum less than 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

Example details omitted.

Constraints

m == mat.length
n == mat[i].length
1 <= m, n <= 300
0 <= mat[i][j] <= 104
0 <= threshold <= 105

Solution Approach

Binary Search on Side Length

We perform binary search over possible side lengths of the square, from 0 to the minimum of the number of rows or columns in the matrix. For each side length, we check if a square of that size exists with the sum less than or equal to the threshold.

Prefix Sum Array

To efficiently calculate the sum of any square in the matrix, we use a 2D prefix sum array. This allows us to compute the sum of any submatrix in constant time, reducing the time complexity of checking each square.

Sliding Window Approach for Sum Calculation

For each square size in the binary search, we use a sliding window technique to move across the matrix and check the sum of elements in all possible squares of that size using the prefix sum array.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution depends on the binary search for the side length (O(log(min(m, n)))) and the sum calculation for each side length using the prefix sum (O(m * n)). Thus, the overall time complexity is O(log(min(m, n)) * m * n). The space complexity is O(m * n) due to the storage of the prefix sum array.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: 2D Prefix Sum + Binary Search

We can precompute a 2D prefix sum array $s$, where $s[i + 1][j + 1]$ represents the sum of elements in the matrix $mat$ from $(0, 0)$ to $(i, j)$. With this, we can calculate the sum of elements in any square region in $O(1)$ time.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

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

Continue Practicing

#363 max sum of rectangle no larger than k #1444 number of ways of cutting a pizza #1508 range sum of sorted subarray sums