Maximum Side Length of a Square with Sum Less than or Equal to Threshold solution and explanation
Google
9 more videos on this problem
Maximum Side Length of a Square with Sum Less than or Equal to Threshold | 2 Ways | Leetcode 1292codestorywithMIK · 1:01:20 · 10K views
LeetCode 1292. Maximum Side Length of a Square with Sum Less than or Equal to ThresholdHappy Coding · 21:49 · 3K views
花花酱 LeetCode 1292. Max Length of a Square with Sum Less than or Equal to Threshold - 刷题找工作 EP286Hua Hua · 18:38 · 3K views
Leetcode 1292: Maximum Side Length of a Square with Sum Less than or Equal to ThresholdAlgorithms Casts · 33:56 · 2K views
Leetcode 1292 solution Maximum Side Length of a Square with Sum Less than or Equal to ThresholdBaozi Training · 10:06 · 1K views
1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold | Leetcode DailyLeetcode Daily · 9:31 · 1K views
Maximum Side Length of a Square with Sum Less than or Equal to Threshold | LeetCode 1292codeTips · 25:59 · 708 views
Maximum Side Length of a Square with Sum Less than or Equal to Threshold | LeetCode 1292 🔥 Study Placement · 43:02 · 685 views
Daily Leetcode #2120: Jan 19, 2026 - 1292. Maximum Side Length of a Square with Sum Less than..Programming Live with Larry · 11:29 · 605 views
1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold (binary searchLetsCode · 18:03 · 418 views
The problem
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.lengthn == mat[i].length1 <= m, n <= 3000 <= mat[i][j] <= 1040 <= threshold <= 105
Approach overview
Problem Overview: You are given an m x n matrix and a threshold. The task is to find the largest possible square submatrix whose total sum is less than or equal to the threshold. The result is the side length of that square.
Approach 1: Prefix Sum + Iteration (Time: O(m * n * min(m,n)), Space: O(m * n))
This approach builds a 2D prefix sum matrix so you can query the sum of any square in constant time. After preprocessing, iterate through each cell and attempt to expand the square size from that position. Using the prefix matrix, compute the sum of a candidate square with the formula sum(x1,y1,x2,y2) in O(1). Continue increasing the side length while the square sum remains ≤ threshold. This method is straightforward and demonstrates correct use of prefix sums, but it checks many possible square sizes.
Approach 2: Binary Search on Side Length (Time: O(m * n * log(min(m,n))), Space: O(m * n))
This approach still relies on a 2D prefix sum but reduces unnecessary checks using binary search. Instead of testing every square size, search the possible side length range from 0 to min(m,n). For a candidate size k, scan the matrix and use the prefix sum to compute each k×k square sum in O(1). If any square satisfies the threshold constraint, the size is valid and you try a larger one. Otherwise, search smaller sizes. The monotonic property (if size k works, all smaller sizes work) makes binary search effective.
The prefix matrix itself is computed in O(m*n) using cumulative sums from the matrix. Each square sum query becomes a constant-time subtraction of four prefix values.
Recommended for interviews: Binary search with prefix sum is the approach most interviewers expect. A brute-force square scan shows you understand the problem, but combining prefix sums with binary search demonstrates algorithmic optimization and familiarity with matrix range queries.
Approach 1: Using Prefix Sum and Iteration
This approach involves calculating the prefix sum matrix which allows for constant time computation of any sub-matrix sum. We then iterate over possible top-left corners for squares and check if the sum of the square area does not exceed the threshold using the prefix sum matrix.
def maxSideLength(mat, threshold):
m, n = len(mat), len(mat[0])
prefixSum = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
prefixSum[i][j] = mat[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1]
maxSide = 0
for i in range(1, m + 1):
for j in range(1, n + 1):
for k in range(maxSide, min(m, n)):
ni, nj = i + k, j + k
if ni > m or nj > n:
break
sum_area = prefixSum[ni][nj] - prefixSum[i-1][nj] - prefixSum[ni][j-1] + prefixSum[i-1][j-1]
if sum_area <= threshold:
maxSide = k + 1
return maxSideclass Solution {
public int maxSideLength(int[][] mat, int threshold) {
int m = mat.length, n = mat[0].length;
int[][] prefixSum = new int[m + 1][n + 1];
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
prefixSum[i][j] = mat[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1];
}
}
int maxSide = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = maxSide; k < m && k < n; ++k) {
int ni = i + k, nj = j + k;
if (ni > m || nj > n) break;
int sum = prefixSum[ni][nj] - prefixSum[i-1][nj] - prefixSum[ni][j-1] + prefixSum[i-1][j-1];
if (sum <= threshold) {
maxSide = k + 1;
}
}
}
}
return maxSide;
}
}#include <vector>
using namespace std;
int maxSideLength(vector<vector<int>>& mat, int threshold) {
int m = mat.size(), n = mat[0].size();
vector<vector<int>> prefixSum(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
prefixSum[i][j] = mat[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1];
}
}
int maxSide = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = maxSide; k < m && k < n; ++k) {
int ni = i + k, nj = j + k;
if (ni > m || nj > n) break;
int sum = prefixSum[ni][nj] - prefixSum[i-1][nj] - prefixSum[ni][j-1] + prefixSum[i-1][j-1];
if (sum <= threshold) {
maxSide = k + 1;
}
}
}
}
return maxSide;
}function maxSideLength(mat, threshold) {
const m = mat.length, n = mat[0].length;
const prefixSum = Array.from({length: m+1}, () => Array(n+1).fill(0));
for (let i = 1; i <= m; ++i) {
for (let j = 1; j <= n; ++j) {
prefixSum[i][j] = mat[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1];
}
}
let maxSide = 0;
for (let i = 1; i <= m; ++i) {
for (let j = 1; j <= n; ++j) {
for (let k = maxSide; k < Math.min(m, n); ++k) {
const ni = i + k, nj = j + k;
if (ni > m || nj > n) break;
const sum = prefixSum[ni][nj] - prefixSum[i-1][nj] - prefixSum[ni][j-1] + prefixSum[i-1][j-1];
if (sum <= threshold) {
maxSide = k + 1;
}
}
}
}
return maxSide;
}#include <stdio.h>
#include <string.h>
int maxSideLength(int** mat, int matSize, int* matColSize, int threshold) {
int m = matSize, n = matColSize[0];
int prefixSum[m+1][n+1];
memset(prefixSum, 0, sizeof(prefixSum));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
prefixSum[i][j] = mat[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1];
}
}
int maxSide = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = maxSide; k < m && k < n; ++k) {
int ni = i + k, nj = j + k;
if (ni > m || nj > n) break;
int sum = prefixSum[ni][nj] - prefixSum[i-1][nj] - prefixSum[ni][j-1] + prefixSum[i-1][j-1];
if (sum <= threshold) {
maxSide = k + 1;
}
}
}
}
return maxSide;
}public class Solution {
public int MaxSideLength(int[][] mat, int threshold) {
int m = mat.Length, n = mat[0].Length;
int[,] prefixSum = new int[m+1, n+1];
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
prefixSum[i, j] = mat[i-1][j-1] + prefixSum[i-1, j] + prefixSum[i, j-1] - prefixSum[i-1, j-1];
}
}
int maxSide = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = maxSide; k < m && k < n; ++k) {
int ni = i + k, nj = j + k;
if (ni > m || nj > n) break;
int sum = prefixSum[ni, nj] - prefixSum[i-1, nj] - prefixSum[ni, j-1] + prefixSum[i-1, j-1];
if (sum <= threshold) {
maxSide = k + 1;
}
}
}
}
return maxSide;
}
}This solution implements the prefix sum and uses nested loops to determine the area sums efficiently to find the maximum square size.
We use Python list comprehensions to create a nested list for the prefix sums.
Time Complexity: O(m*n*k) where k is constrained by min(m, n) and bounded by the possibilities processed.
Space Complexity: O(m*n)
Approach 2: Binary Search on Side Length
This approach utilizes binary search to find the maximum possible size of a square whose sum does not exceed the given threshold. It initially calculates a prefix sum matrix and then performs binary search based on potential square side lengths.
def maxSideLength(mat, threshold):
m, n = len(mat), len(mat[0])
prefixSum = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
prefixSum[i][j] = mat[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1]
def isValid(r, c, k):
return prefixSum[r][c] - prefixSum[r-k][c] - prefixSum[r][c-k] + prefixSum[r-k][c-k] <= threshold
low, high, answer = 0, min(m, n), 0
while low <= high:
mid = (low + high) // 2
if any(isValid(i, j, mid) for i in range(mid, m + 1) for j in range(mid, n + 1)):
answer = mid
low = mid + 1
else:
high = mid - 1
return answerclass Solution {
private boolean isValid(int[][] prefixSum, int r, int c, int k, int threshold) {
return prefixSum[r][c] - prefixSum[r-k][c] - prefixSum[r][c-k] + prefixSum[r-k][c-k] <= threshold;
}
public int maxSideLength(int[][] mat, int threshold) {
int m = mat.length, n = mat[0].length;
int[][] prefixSum = new int[m + 1][n + 1];
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
prefixSum[i][j] = mat[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1];
}
}
int low = 0, high = Math.min(m, n), answer = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
boolean found = false;
for (int i = mid; i <= m && !found; ++i) {
for (int j = mid; j <= n && !found; ++j) {
if (isValid(prefixSum, i, j, mid, threshold)) {
found = true;
}
}
}
if (found) {
answer = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return answer;
}
}#include <vector>
using namespace std;
bool isValid(vector<vector<int>>& prefixSum, int r, int c, int k, int threshold) {
return prefixSum[r][c] - prefixSum[r-k][c] - prefixSum[r][c-k] + prefixSum[r-k][c-k] <= threshold;
}
int maxSideLength(vector<vector<int>>& mat, int threshold) {
int m = mat.size(), n = mat[0].size();
vector<vector<int>> prefixSum(m+1, vector<int>(n+1, 0));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
prefixSum[i][j] = mat[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1];
}
}
int low = 0, high = min(m, n), answer = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
bool found = false;
for (int i = mid; i <= m && !found; ++i) {
for (int j = mid; j <= n && !found; ++j) {
if (isValid(prefixSum, i, j, mid, threshold)) {
found = true;
}
}
}
if (found) {
answer = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return answer;
}function maxSideLength(mat, threshold) {
const m = mat.length, n = mat[0].length;
const prefixSum = Array.from({length: m+1}, () => Array(n+1).fill(0));
for (let i = 1; i <= m; ++i) {
for (let j = 1; j <= n; ++j) {
prefixSum[i][j] = mat[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1];
}
}
const isValid = (r, c, k) => prefixSum[r][c] - prefixSum[r-k][c] - prefixSum[r][c-k] + prefixSum[r-k][c-k] <= threshold;
let low = 0, high = Math.min(m, n), answer = 0;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
let found = false;
for (let i = mid; i <= m && !found; ++i) {
for (let j = mid; j <= n && !found; ++j) {
if (isValid(i, j, mid)) {
found = true;
}
}
}
if (found) {
answer = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return answer;
}#include <stdio.h>
#include <string.h>
int isValid(int** prefixSum, int r, int c, int k, int threshold) {
return prefixSum[r][c] - prefixSum[r-k][c] - prefixSum[r][c-k] + prefixSum[r-k][c-k] <= threshold;
}
int maxSideLength(int** mat, int matSize, int* matColSize, int threshold) {
int m = matSize, n = matColSize[0];
int prefixSum[m+1][n+1];
memset(prefixSum, 0, sizeof(prefixSum));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
prefixSum[i][j] = mat[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1];
}
}
int low = 0, high = (m < n ? m : n), answer = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
int found = 0;
for (int i = mid; i <= m && !found; ++i) {
for (int j = mid; j <= n && !found; ++j) {
if (isValid(prefixSum, i, j, mid, threshold)) {
found = 1;
}
}
}
if (found) {
answer = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return answer;
}public class Solution {
private bool IsValid(int[,] prefixSum, int r, int c, int k, int threshold) {
return prefixSum[r, c] - prefixSum[r-k, c] - prefixSum[r, c-k] + prefixSum[r-k, c-k] <= threshold;
}
public int MaxSideLength(int[][] mat, int threshold) {
int m = mat.Length, n = mat[0].Length;
int[,] prefixSum = new int[m+1, n+1];
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
prefixSum[i, j] = mat[i-1][j-1] + prefixSum[i-1, j] + prefixSum[i, j-1] - prefixSum[i-1, j-1];
}
}
int low = 0, high = Math.Min(m, n), answer = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
bool found = false;
for (int i = mid; i <= m && !found; ++i) {
for (int j = mid; j <= n && !found; ++j) {
if (IsValid(prefixSum, i, j, mid, threshold)) {
found = true;
}
}
}
if (found) {
answer = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return answer;
}
}The Python solution sets up and utilizes a binary search methodology, checking for validity of the midpoints determined by scanning all valid sums within the threshold limit, leveraging prefix sums for computative efficiency.
Time Complexity: O(m*n*log(min(m, n)))
Space Complexity: O(m*n)
Approach 3: 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.
Next, we can use binary search to find the maximum side length. We enumerate the side length k of the square, and then iterate through all possible top-left positions (i, j) of the square. We can calculate the sum of elements v for the square. If v leq threshold, it indicates that there exists a square region with side length k whose sum is less than or equal to the threshold; otherwise, no such square exists for the current k.
The time complexity is O(m times n times log min(m, n)), and the space complexity is O(m times n).
function maxSideLength(mat: number[][], threshold: number): number {
const m = mat.length;
const n = mat[0].length;
const s: number[][] = Array(m + 1)
.fill(0)
.map(() => Array(n + 1).fill(0));
for (let i = 1; i <= m; ++i) {
for (let j = 1; j <= n; ++j) {
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + mat[i - 1][j - 1];
}
}
const check = (k: number): boolean => {
for (let i = 0; i < m - k + 1; ++i) {
for (let j = 0; j < n - k + 1; ++j) {
if (s[i + k][j + k] - s[i + k][j] - s[i][j + k] + s[i][j] <= threshold) {
return true;
}
}
}
return false;
};
let l = 0;
let r = Math.min(m, n);
while (l < r) {
const mid = (l + r + 1) >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}func maxSideLength(mat [][]int, threshold int) int {
m, n := len(mat), len(mat[0])
s := make([][]int, m+1)
for i := range s {
s[i] = make([]int, n+1)
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + mat[i-1][j-1]
}
}
check := func(k int) bool {
for i := 0; i < m-k+1; i++ {
for j := 0; j < n-k+1; j++ {
if s[i+k][j+k]-s[i][j+k]-s[i+k][j]+s[i][j] <= threshold {
return true
}
}
}
return false
}
l, r := 0, min(m, n)
for l < r {
mid := (l + r + 1) >> 1
if check(mid) {
l = mid
} else {
r = mid - 1
}
}
return l
}impl Solution {
pub fn max_side_length(mat: Vec<Vec<i32>>, threshold: i32) -> i32 {
let m = mat.len();
let n = mat[0].len();
let mut s = vec![vec![0; n + 1]; m + 1];
for i in 1..=m {
for j in 1..=n {
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + mat[i - 1][j - 1];
}
}
let check = |k: usize| -> bool {
for i in 0..=m - k {
for j in 0..=n - k {
if s[i + k][j + k] - s[i][j + k] - s[i + k][j] + s[i][j] <= threshold {
return true;
}
}
}
false
};
let mut l = 0usize;
let mut r = m.min(n);
while l < r {
let mid = (l + r + 1) >> 1;
if check(mid) {
l = mid;
} else {
r = mid - 1;
}
}
l as i32
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using Prefix Sum and Iteration | Time Complexity: O(m*n*k) where k is constrained by min(m, n) and bounded by the possibilities processed. |
| Binary Search on Side Length | Time Complexity: O(m*n*log(min(m, n))) |
| 2D Prefix Sum + Binary Search | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix Sum + Iteration | O(m * n * min(m,n)) | O(m * n) | When implementing a straightforward solution using prefix sums without optimization |
| Binary Search on Side Length + Prefix Sum | O(m * n * log(min(m,n))) | O(m * n) | Preferred approach when matrix dimensions are large and you want fewer square checks |
Frequently asked questions
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.
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.
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.
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.