Maximum Side Length Of A Square With Sum Less Than Or Equal To Threshold
01 · Problem
You are given an m x n grid mat of non-negative integers and an integer threshold.
Find the largest integer L such that there is at least one L x L square submatrix of mat whose elements add up to at most threshold. Return L, or 0 if no such square exists (that is, every single cell is already greater than threshold).
02 · Examples
mat = [[1,2,1,3],[2,1,2,1],[1,1,1,2],[3,2,1,1]], threshold = 10
2
The top-left 2x2 square has sum 1 + 2 + 2 + 1 = 6 <= 10. All four 3x3 squares have sums of 12 or 14, which exceed 10.
mat = [[4,5],[6,7]], threshold = 3
0
Every single cell is larger than 3, so no square qualifies.
mat = [[5,1,1],[1,1,1],[1,1,9]], threshold = 4
2
The 2x2 square covering rows 0-1 and columns 1-2 contains 1, 1, 1, 1 with sum 4. The only 3x3 square has sum 21.
03 · Constraints
- 011 <= m, n <= 300
- 020 <= mat[i][j] <= 104
- 030 <= threshold <= 105
04 · Optimal complexity
- Time
- O(m * n * log(min(m, n)))
- Space
- O(m * n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.