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

The most efficient approach combines a 2D prefix sum with binary search on the square side length. The prefix sum allows constant-time submatrix sum queries, and binary search reduces the number of candidate square sizes. This results in O(m * n * log(min(m,n))) time and O(m * n) space.

Is Maximum Side Length of a Square with Sum Less than or Equal to Threshold asked at Google/Amazon/Meta?

Matrix prefix sum and submatrix query problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variations of this problem test understanding of 2D prefix sums, matrix traversal, and optimization with binary search.

What data structure is used in Maximum Side Length of a Square with Sum Less than or Equal to Threshold?

The key data structure is a 2D prefix sum array. It stores cumulative sums so the sum of any submatrix can be computed with four lookups. The algorithm also uses binary search to efficiently determine the maximum valid square size.

What is the time complexity of Maximum Side Length of a Square with Sum Less than or Equal to Threshold?

The optimal solution runs in O(m * n * log(min(m,n))) time using binary search on the side length and prefix sums for constant-time square sum checks. Building the prefix sum matrix takes O(m * n) time and space.

Description Hints 3 Solution Video 1:01:20

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

Q: Is Maximum Side Length of a Square with Sum Less than or Equal to Threshold easy or hard?

The problem is rated Medium because it requires combining two concepts: 2D prefix sums and binary search optimization. Developers comfortable with matrix prefix sums can implement the base solution quickly, while the optimized version requires recognizing the monotonic property of square sizes.

Q: Maximum Side Length of a Square with Sum Less than or Equal to Threshold Python/Java solution

Implementations typically build a prefix sum matrix first, then either iterate through square sizes or apply binary search. The same logic works across Python, Java, C++, and JavaScript because the algorithm relies on simple array operations and constant-time prefix calculations.

Q: How to solve Maximum Side Length of a Square with Sum Less than or Equal to Threshold in O(m*n log n)?

First compute a 2D prefix sum so any square sum can be calculated in O(1). Then binary search the side length between 0 and min(m,n). For each candidate size, scan the matrix and check all k×k squares using the prefix matrix. If a valid square exists, increase the size; otherwise decrease it.

Medium65.4% acceptance4 companies

Given a m x n matrix mat and an integer threshold, return the maximum side-length of a square with a sum less than or equal to threshold or return 0 if there is no such square.

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 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

Constraints:

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

Asked at 4 companies

Fractal Analytics IMC

Google Amazon

Topics

Hints open one at a time

Hint 1

Store prefix sum of all grids in another 2D array.

Hint 2

Try all possible solutions and if you cannot find one return -1.

Hint 3

If x is a valid answer then any y < x is also valid answer. Use binary search to find answer.

1:01:20

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

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

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]]
4

Input

[[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]]
1

Your code is saved on this device.Solution