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 <= 105Problem 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.
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.
This solution computes a prefix sum matrix of size (m+1)x(n+1). It then iterates over each possible starting point and potential square sizes contained within the matrix. The prefixed summed values allow for rapid calculation of the sum for any rectilinear sub-section of the matrix.
Time Complexity: O(m*n*k) where k is constrained by min(m, n) and bounded by the success of squares.
Space Complexity: O(m*n)
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.
This C implementation uses a binary search on the possible side lengths to efficiently determine if a square of that side can have a sum less than or equal to the threshold. The helper function isValid checks if the sum of the square area from the prefix sum matrix fits within the given threshold.
Time Complexity: O(m*n*log(min(m, n)))
Space Complexity: O(m*n)
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).
| 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 success of squares. |
| Binary Search on Side Length | Time Complexity: O(m*n*log(min(m, n))) |
| 2D Prefix Sum + Binary Search | — |
| 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 |
Maximum Side Length of a Square with Sum Less than or Equal to Threshold | 2 Ways | Leetcode 1292 • codestorywithMIK • 10,272 views views
Watch 9 more video solutions →Practice Maximum Side Length of a Square with Sum Less than or Equal to Threshold with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor