Maximum Side Length of a Square with Sum Less than or Equal to Threshold
Maximum Side Length of a Square with Sum Less than or Equal to Threshold solution: step-by-step approach, complexity and code in Python, Java, C++ and…
Maximum Side Length of a Square with Sum Less than or Equal to Threshold is a medium coding problem on arrays, binary search and matrix, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Binary Search, Matrix, Prefix Sum
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an m x n grid mat of non-negative integers and an integer threshold.
A square is any k x k block of adjacent cells (k >= 1). Return the largest side length k such that at least one k x k square has a cell sum of at most threshold. Return 0 if even a single cell exceeds the threshold everywhere.
Example 1
Input: mat = [[2,2,5],[2,2,5],[5,5,5]], threshold = 8
Output: 2
Explanation: The top-left 2 x 2 block sums to 8; the whole 3 x 3 grid sums to 33.
Example 2
Input: mat = [[2,3],[4,5]], threshold = 1
Output: 0
Example 3
Input: mat = [[1,1,1],[1,1,1],[1,1,1]], threshold = 9
Output: 3
Constraints
1 <= m, n <= 3000 <= mat[i][j] <= 10^40 <= threshold <= 10^5
Hints for Maximum Side Length of a Square with Sum Less than or Equal to Threshold
Hint 1
With a 2-D prefix-sum table, the sum of any square is four lookups.
Hint 2
If some
k x ksquare fits under the threshold, a(k - 1) x (k - 1)square inside it does too — values are non-negative.Hint 3
That monotonicity lets you binary-search
k, checking every placement of ak x ksquare per step.
How to solve Maximum Side Length of a Square with Sum Less than or Equal to Threshold
Precompute 2-D prefix sums so any square's sum costs O(1). Feasibility of side k is monotone (shrinking a square never raises its sum), so binary-search the largest feasible k.
Approach
- Build
P[i][j]= sum ofmat[0..i-1][0..j-1]for0 <= i <= m,0 <= j <= n. - The square with top-left
(i, j)and sideksums toP[i+k][j+k] - P[i][j+k] - P[i+k][j] + P[i][j]. fits(k): true if any placement of ak x ksquare sums to at mostthreshold.- Binary-search
kin[0, min(m, n)], moving up whenfits(mid)holds;k = 0always fits.
Why it works
Every cell is non-negative, so a sub-square of a fitting square also fits: the predicate fits(k) is true up to some largest k and false after it. Binary search on such a predicate lands exactly on that boundary, and the prefix-sum identity is inclusion–exclusion over four rectangles anchored at the origin.
Complexity
- Time —
O(m · n · log(min(m, n))) - Space —
O(m · n)
Pitfalls
- Use the upper-middle
(lo + hi + 1) / 2when movinglo = mid, or the loop never ends. - Return 0, not 1, when every single cell is above the threshold.
- Off-by-one in the prefix table: give it an extra zero row and column.
Reference solution
Python
from typing import List
def maxSideLength(mat: List[List[int]], threshold: int) -> int:
m, n = len(mat), len(mat[0])
P = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m):
for j in range(n):
P[i + 1][j + 1] = P[i][j + 1] + P[i + 1][j] - P[i][j] + mat[i][j]
def fits(k):
for i in range(m - k + 1):
for j in range(n - k + 1):
if P[i + k][j + k] - P[i][j + k] - P[i + k][j] + P[i][j] <= threshold:
return True
return False
lo, hi = 0, min(m, n)
while lo < hi:
mid = (lo + hi + 1) // 2
if fits(mid):
lo = mid
else:
hi = mid - 1
return loJava
public static int maxSideLength(int[][] mat, int threshold) {
int m = mat.length, n = mat[0].length;
int[][] P = new int[m + 1][n + 1];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
P[i + 1][j + 1] = P[i][j + 1] + P[i + 1][j] - P[i][j] + mat[i][j];
int lo = 0, hi = Math.min(m, n);
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
boolean ok = false;
for (int i = 0; i + mid <= m && !ok; i++)
for (int j = 0; j + mid <= n; j++)
if (P[i + mid][j + mid] - P[i][j + mid] - P[i + mid][j] + P[i][j] <= threshold) { ok = true; break; }
if (ok) lo = mid; else hi = mid - 1;
}
return lo;
}C++
int maxSideLength(vector<vector<int>>& mat, int threshold) {
int m = mat.size(), n = mat[0].size();
vector<vector<int>> P(m + 1, vector<int>(n + 1, 0));
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
P[i + 1][j + 1] = P[i][j + 1] + P[i + 1][j] - P[i][j] + mat[i][j];
int lo = 0, hi = min(m, n);
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
bool ok = false;
for (int i = 0; i + mid <= m && !ok; i++)
for (int j = 0; j + mid <= n; j++)
if (P[i + mid][j + mid] - P[i][j + mid] - P[i + mid][j] + P[i][j] <= threshold) { ok = true; break; }
if (ok) lo = mid; else hi = mid - 1;
}
return lo;
}JavaScript
var maxSideLength = function(mat, threshold) {
var m = mat.length, n = mat[0].length;
var P = [];
for (var i = 0; i <= m; i++) P.push(new Array(n + 1).fill(0));
for (var r = 0; r < m; r++)
for (var c = 0; c < n; c++)
P[r + 1][c + 1] = P[r][c + 1] + P[r + 1][c] - P[r][c] + mat[r][c];
var fits = function(k) {
for (var a = 0; a + k <= m; a++)
for (var b = 0; b + k <= n; b++)
if (P[a + k][b + k] - P[a][b + k] - P[a + k][b] + P[a][b] <= threshold) return true;
return false;
};
var lo = 0, hi = Math.min(m, n);
while (lo < hi) {
var mid = (lo + hi + 1) >> 1;
if (fits(mid)) lo = mid; else hi = mid - 1;
}
return lo;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Search