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 Problem Description:
Given an m * 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.
Examples:
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 a square with a sum less than or equal to 4 is 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
Explanation: Every element in the matrix is 2, which is greater than the threshold 1.
Since even the smallest 1×1 square has a sum of 2, there is no possible square with a sum ≤ 1.
Therefore, the answer is 0.
Constraints:
m == mat.length
n == mat[i].length
1 ≤ m, n ≤ 300
0 ≤ mat[i][j] ≤ 10⁴
0 ≤ threshold ≤ 10⁵
Brute Force Approach
To approach the problem, we are given an m × n matrix mat and an integer threshold, and we need to determine the maximum possible side length of a square submatrix whose sum is less than or equal to threshold. If no such square exists, return 0. Our goal is to find the maximum value of nums[index] while ensuring that the sum of the array remains within maxSum.
A natural way to approach this problem is to check all possible squares that can be formed in the matrix. We iterate over every possible starting cell and try to expand the square size while keeping the sum within the given threshold. The goal is to find the largest valid square where the sum of elements is ≤ threshold.
How to Implement It?
- Iterate over each cell as a possible top-left corner of a square.
- Expand the square by increasing its side length one by one until it either:
- Exceeds the matrix bounds, or
- Exceeds the threshold sum.
- Track the maximum valid square size found across all positions.
For example, consider an example:
mat = [
[1, 1, 3, 2, 4],
[1, 1, 3, 2, 4],
[1, 1, 3, 2, 4]
]
threshold = 4
Step-by-Step Process
- Start at (0,0):
- 1x1 → Sum = 1 (Valid)
- 2x2 → Sum = 4 (Valid)
- 3x3 → Sum = 9 (Invalid) → Stop expanding
- Move to (0,1):
- 1x1 → Sum = 1 (Valid)
- 2x2 → Sum = 4 (Valid)
- 3x3 → Sum = 9 (Invalid) → Stop expanding
- Continue for all cells and track the maximum valid square size.
Final Output: 2
(The largest valid square has a side length of 2.)
We can implement the same approach in a more structured and organized manner.
Let's see how:
What can be the minimum value of the square’s side length?
The minimum side length of the square should be 1, as each submatrix must contain at least one element. If we assume all other elements in the matrix are greater than threshold, then even the smallest 1 × 1 square would exceed the threshold, making 1 the only possible smallest value.
What would be the maximum value of the square’s side length?
The maximum possible side length should be min(m, n) in the best-case scenario. This occurs when the entire sum of the square is within the given threshold, and the largest square that can fit in the matrix is min(m, n) × min(m, n).
Thus, our search space for the square’s side length ranges from 1 to min(m, n). The problem then reduces to finding the largest possible side length that satisfies the given constraints.
A brute-force approach would be to iterate over all possible side lengths from 1 to min(m, n) and check whether it is possible to construct a square submatrix satisfying the sum condition.
Consider mat = [[1,1,3,2,4,3,2], [1,1,3,2,4,3,2], [1,1,3,2,4,3,2]],
threshold = 4
We start by setting the smallest possible side length as 1 and the largest possible value as min(m, n) = 3 (since the matrix is 3 × 7).
Now, we check whether it is possible to construct a valid square for different values of side length:
- If side length = 1, we can construct multiple 1×1 squares, and since some of these contain values ≤ 4, it is valid.
- If side length = 2, we can construct a 2×2 square where the sum is ≤ 4.
- If side length = 3, we cannot construct a 3×3 square whose sum is ≤ 4, as the smallest possible 3×3 square has a sum exceeding 4.
- Any square of size > 3 will also exceed the threshold.
Since 3 is the first point where it's impossible, we return 2, the point before it. Thus, the answer is 2.
We can see that every square with a side length from 1 to maxSide allows us to construct a valid submatrix. But as soon as we try maxSide + 1 or more, it’s no longer possible because the sum exceeds threshold.
Let’s define maxSide as the maximum possible side length of a square submatrix whose sum is less than or equal to threshold. Any value greater than maxSide would make it impossible to construct a valid square within the threshold constraint. However, any value from 1 to maxSide ensures that we can construct a submatrix satisfying all the given conditions. On the other hand, any value from maxSide + 1 and beyond will never satisfy the constraints, as the sum of the submatrix would exceed threshold.
How can we determine if a square is valid given its side length (Real-World Example)?
Alright! Imagine you have a big grid full of numbers, and you want to quickly find the sum of a specific k × k square within it.
How would you do it?
The most straightforward way would be to simply loop through every element inside the k × k submatrix, add them up, and return the sum. While this works, it's very slow when dealing with large grids.
For example, if we have a 1000 × 1000 grid and we need to compute the sum of many submatrices, looping through k² elements each time would be painfully slow!
We need something smarter—a way to get the sum instantly in O(1) time instead of O(k²).
How can we precompute sums for fast queries?
Let’s think of a better way. Instead of computing sums from scratch each time, what if we could precompute some values so that we can retrieve the sum in constant time?
Here's the idea:
- If we want to know the sum of any submatrix, it must already be stored somewhere.
- We can build a matrix where each cell stores the sum of all elements from (0,0) to that cell.
- This way, instead of recalculating, we can just retrieve precomputed sums and do some quick arithmetic.
How do we construct such a matrix?
That’s where prefix sum comes in!
How Do We Construct a Prefix Sum Matrix?
A prefix sum matrix is a special matrix where each cell prefixSum[i][j] stores the sum of all elements from the top-left corner (0,0) to (i,j).
This allows each cell to "remember" the cumulative sum of everything above and to the left of it. By precomputing these values, we can instantly compute the sum of any submatrix in constant time O(1).
What is a Prefix Sum Matrix?
A prefix sum matrix helps us compute the sum of any submatrix in constant time O(1) instead of looping through all the elements. Think of it as a way to "precompute" sums so that we can later retrieve them instantly.
How Do We Compute the Prefix Sum for Any Cell?
To calculate prefixSum[i][j], we must carefully add up relevant values while ensuring we do not double-count any region.
The key idea is to sum up all elements above and to the left while subtracting the overlapping part. Let’s break it down:
What We Need to Add?
- The current cell’s value.(grid[i][j])
- Adds all elements above the current cell (same column). (prefixSum[i-1][j] )
- Adds all elements left of the current cell (same row). (prefixSum[i][j-1] )
What We Need to Subtract?
- The overlapping part (top-left region) is added twice in steps 2 and 3, so we subtract it once to correct the double-counting.(prefixSum[i-1][j-1])
Let's understand with an example:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16Now, let's compute prefixSum[2][2] (for element grid[2][2] = 11).
Step 1: Start with grid[2][2] (The current cell value): 11
Step 2: Add prefixSum[1][2] (Sum of all elements above row 2, same column 2)
prefixSum[1][2] = 1 + 2 + 3 + 5 + 6 + 7 = 24
New sum: 11 + 24 = 35
Step 3: Add prefixSum[2][1] (Sum of all elements left of column 2, same row 2)
prefixSum[2][1] = 1 + 5 + 9 + 2 + 6 + 10 = 33
New sum: 35 + 33 = 68
Step 4: Subtract prefixSum[1][1] (It was added twice, so remove overlap)
prefixSum[1][1] = 1 + 2 + 5 + 6 = 14
Final sum: 68 - 14 = 54
General Formula for Prefix Sum
From the above steps, we derive the formula:
prefixSum[i][j] = grid[i][j] + prefixSum[i−1][j] + prefixSum[i][j−1] − prefixSum[i−1][j−1]
By following this formula, we can efficiently precompute the prefix sum matrix for any given grid. Once this matrix is computed, we can retrieve the sum of any submatrix in O(1) time, making it highly efficient for range sum queries!
Now that we understand what a prefix sum matrix is, let’s see how we can use it to quickly calculate the sum of any submatrix in constant time O(1).
How Can We Calculate the Sum of a Submatrix Using Prefix Sum?
To find the sum of any submatrix efficiently, we use the precomputed prefix sum values instead of looping through every element manually.
Let’s say we have a submatrix of side length k, where:
- Top-left corner = (i, j)
- Bottom-right corner = (i+k-1, j+k-1)
Our goal is to quickly find the sum of all elements inside this submatrix.
Using the prefix sum matrix, we can efficiently retrieve the sum using inclusion-exclusion.
Think of the prefixSum[i+k-1][j+k-1] as containing the sum of everything from (0,0) to (i+k-1, j+k-1).
However, it includes extra regions that we don’t want inside our submatrix:
- What do we have initially?
We start with prefixSum[i+k-1][j+k-1], which contains the total sum from the top-left (0,0) to the bottom-right (i+k-1, j+k-1). - What extra parts need to be removed?
prefixSum[i-1][j+k-1] → This removes the extra region above the submatrix.
prefixSum[i+k-1][j-1] → This removes the extra region left of the submatrix. - What got removed twice?
The overlap (top-left corner that was removed twice) needs to be added back:
prefixSum[i-1][j-1] → This was subtracted twice, so we add it back once.
Now, we have the exact sum of the k × k submatrix!
To find the sum of this submatrix, we need to extract only the numbers inside it.
Step 1: Start with the Total Sum from (0,0) to (i+k-1, j+k-1)
The value prefixSum[i+k-1][j+k-1] gives us the sum of all elements from (0,0) to (i+k-1, j+k-1).
However, this includes extra regions that we don’t want.
Step 2: Subtract the Extra Rows Above
The prefix sum includes all elements from (0,0) to (i+k-1, j+k-1), but we only need elements from row i onwards.
To remove the unnecessary rows above row i, we subtract prefixSum[i-1][j+k-1], which gives the sum of the excluded region above.
Step 3: Subtract the Extra Columns to the Left
Similarly, we need to remove the unnecessary columns to the left of column j.
The sum of these extra columns is given by prefixSum[i+k-1][j-1], so we subtract it.
Step 4: Add Back the Overlapping Extra Region
We subtracted both the extra rows above and columns to the left, but the top-left overlapping region (which was removed twice) also got removed twice.
To correct this, we add it back using prefixSum[i-1][j-1].
Let’s take an example matrix:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16Now, let’s say we want to find the sum of the 2 × 2 submatrix starting at (1,1) (zero-indexed), i.e.,
6 7
10 11Step 1: Get the Total Sum from (0,0) to (2,2)
From the prefix sum matrix, this value is:
prefixSum[2][2] = 1 + 2 + 3 + 5 + 6 + 7 + 9 + 10 + 11 = 54
Step 2: Subtract the Extra Rows Above (Row 0)
prefixSum[0][2] = 1 + 2 + 3 = 6
New sum = 54 - 6 = 48
Step 3: Subtract the Extra Columns to the Left (Column 0)
prefixSum[2][0] = 1 + 5 + 9 = 15
New sum = 48 - 15 = 33
Step 4: Add Back the Overlapping Extra Region
prefixSum[0][0]=1
Final sum = 33 + 1 = 34
This matches the sum of the 2 × 2 submatrix: 6 + 7 + 10 + 11 = 34
Deriving the General Formula
From the explanation above, the sum of a k × k submatrix with top-left corner at (i, j) and bottom-right corner at (i+k-1, j+k-1) is:
sum = prefixSum[i+k−1][j+k−1] − prefixSum[i−1][j+k−1] − prefixSum[i+k−1][j−1] + prefixSum[i−1][j−1]
Where:
- prefixSum[i+k-1][j+k-1] → Total sum from (0,0) to (i+k-1, j+k-1)
- prefixSum[i-1][j+k-1] → Remove extra rows above
- prefixSum[i+k-1][j-1] → Remove extra columns to the left
- prefixSum[i-1][j-1] → Add back the double-subtracted region
Thus, we can now compute any k × k submatrix sum in O(1) time instead of O(k²)!
Let's understand with an example:
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
We try increasing k (submatrix size) until the sum exceeds the threshold.
Step 1: k = 1 (1×1 submatrix)
- Any single element submatrix has a sum ≤ 4.
- Valid k = 1
Step 2: k = 2 (2×2 submatrices)
Checking mat[0][0] to mat[1][1]:[
[1, 1],
[1, 1]
]
- Sum = 1+1+1+1 = 4 (Valid)
Step 3: k = 3 (3×3 submatrices)
None of the submatrix has sum <= threshold
Since k = 3 is invalid, the max valid k is 2.
Final Answer: k = 2
Steps to Implement the Solution:
Understand the Problem
Given an m × n matrix mat and an integer threshold, find the largest possible square submatrix with sum ≤ threshold.
Use Prefix Sum for Efficient Sum Calculation
Construct a prefix sum matrix prefixSum to compute any submatrix sum in O(1) time.
Build the Prefix Sum Matrix
- Create an n × m matrix (0-based indexing).
- Use the formula:
prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1] + mat[i][j] - Ensure valid boundaries before accessing prefixSum[i-1][j], prefixSum[i][j-1], or prefixSum[i-1][j-1].
Implement the isPossible() Function
- Iterate over all possible top-left corners of submatrices.
- Compute the sum of the current square submatrix using the prefix sum formula:
sum_val = prefixSum[i+size-1][j+size-1] - Subtract prefixSum[i-1][j+size-1] if i > 0.
- Subtract prefixSum[i+size-1][j-1] if j > 0.
- Add prefixSum[i-1][j-1] if both i > 0 and j > 0.
- If any square of the given size satisfies the threshold condition, return true.
Replace Binary Search with Linear Search
- Iterate over possible square sizes from 1 to min(n, m).
- If a valid square of size size exists, update the answer ans = size.
Return the Maximum Valid Square Size
- The last valid size found is returned as the answer.
Maximum Side Length of a Square with Sum Less than or Equal to Threshold leetcode solutions / Code Implementation
1. Maximum Side Length of a Square with Sum Less than or Equal to Threshold solution in c++ Try on Compiler
class Solution {
// Function to check if there exists a square submatrix of given size with sum <= threshold
bool isPossible(vector<vector<int>>& prefixSum, int threshold, int size)
{
// Get the number of rows and columns
int n = prefixSum.size();
int m = prefixSum[0].size();
// Iterate over possible top-left corners of submatrices
for (int i = 0; i + size <= n; i++) {
for (int j = 0; j + size <= m; j++) {
// Compute the sum of the submatrix using prefix sum formula
int sum = prefixSum[i + size - 1][j + size - 1];
if (i > 0) sum -= prefixSum[i - 1][j + size - 1];
if (j > 0) sum -= prefixSum[i + size - 1][j - 1];
if (i > 0 && j > 0) sum += prefixSum[i - 1][j - 1];
// If sum is within threshold, return true
if (sum <= threshold)
return true;
}
}
// Return false if no valid submatrix found
return false;
}
public:
// Function to find the maximum side length of a square submatrix with sum <= threshold
int maxSideLength(vector<vector<int>>& mat, int threshold) {
// Get the number of rows and columns
int n = mat.size();
int m = mat[0].size();
// Initialize the prefix sum matrix (0-based indexing, no extra row/column)
vector<vector<int>> prefixSum(n, vector<int>(m, 0));
// Compute the prefix sum for the matrix
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
prefixSum[i][j] = mat[i][j];
if (i > 0) prefixSum[i][j] += prefixSum[i - 1][j];
if (j > 0) prefixSum[i][j] += prefixSum[i][j - 1];
if (i > 0 && j > 0) prefixSum[i][j] -= prefixSum[i - 1][j - 1];
}
}
// Linear search approach to find max valid side length
int low = 1, high = min(n, m), ans = 0;
// Check for each size from 1 to the smallest dimension of the matrix
for(int i = low; i <= high; i++) {
// If a valid submatrix of this size exists, update answer
if(isPossible(prefixSum, threshold, i)) {
ans = i;
}
}
// Return the maximum valid side length
return ans;
}
};
2. Maximum Side Length of a Square with Sum Less than or Equal to Threshold solution in Java Try on Compiler
class Solution {
// Helper function to check if a square of given size is possible
private boolean isPossible(int[][] prefixSum, int threshold, int size) {
int n = prefixSum.length;
int m = prefixSum[0].length;
// Iterate over all possible top-left corners of submatrices of given size
for (int i = 0; i + size <= n; i++) {
for (int j = 0; j + size <= m; j++) {
// Compute the sum of the current submatrix using the prefix sum matrix
int sum = prefixSum[i + size - 1][j + size - 1];
if (i > 0) sum -= prefixSum[i - 1][j + size - 1];
if (j > 0) sum -= prefixSum[i + size - 1][j - 1];
if (i > 0 && j > 0) sum += prefixSum[i - 1][j - 1];
// If sum is within threshold, return true
if (sum <= threshold) {
return true;
}
}
}
// Return false if no valid submatrix is found
return false;
}
public int maxSideLength(int[][] mat, int threshold) {
int n = mat.length;
int m = mat[0].length;
// Create a prefix sum matrix (0-based indexing, no extra row/column)
int[][] prefixSum = new int[n][m];
// Fill the prefix sum matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
prefixSum[i][j] = mat[i][j];
if (i > 0) prefixSum[i][j] += prefixSum[i - 1][j];
if (j > 0) prefixSum[i][j] += prefixSum[i][j - 1];
if (i > 0 && j > 0) prefixSum[i][j] -= prefixSum[i - 1][j - 1];
}
}
// Linear search approach to find max valid side length
int low = 1, high = Math.min(n, m), ans = 0;
// Iterate over all possible square sizes
for (int i = low; i <= high; i++) {
// Check if a square of size i is possible
if (isPossible(prefixSum, threshold, i)) {
ans = i;
}
}
// Return the maximum valid square size
return ans;
}
}
3. Maximum Side Length of a Square with Sum Less than or Equal to Threshold solution in Python Try on Compiler
class Solution:
def isPossible(self, prefixSum, threshold, size):
n, m = len(prefixSum), len(prefixSum[0])
# Iterate over all possible top-left corners of submatrices of given size
for i in range(n - size + 1):
for j in range(m - size + 1):
# Compute the sum of the current submatrix using the prefix sum matrix
sum_val = prefixSum[i + size - 1][j + size - 1]
if i > 0:
sum_val -= prefixSum[i - 1][j + size - 1]
if j > 0:
sum_val -= prefixSum[i + size - 1][j - 1]
if i > 0 and j > 0:
sum_val += prefixSum[i - 1][j - 1]
# If sum is within threshold, return True
if sum_val <= threshold:
return True
# Return False if no valid submatrix is found
return False
def maxSideLength(self, mat, threshold):
n, m = len(mat), len(mat[0])
# Create a prefix sum matrix (0-based indexing, no extra row/column)
prefixSum = [[0] * m for _ in range(n)]
# Fill the prefix sum matrix
for i in range(n):
for j in range(m):
prefixSum[i][j] = mat[i][j]
if i > 0:
prefixSum[i][j] += prefixSum[i - 1][j]
if j > 0:
prefixSum[i][j] += prefixSum[i][j - 1]
if i > 0 and j > 0:
prefixSum[i][j] -= prefixSum[i - 1][j - 1]
# Linear search approach to find max valid side length
low, high, ans = 1, min(n, m), 0
# Iterate over all possible square sizes
for i in range(low, high + 1):
# Check if a square of size i is possible
if self.isPossible(prefixSum, threshold, i):
ans = i
# Return the maximum valid square size
return ans
4. Maximum Side Length of a Square with Sum Less than or Equal to Threshold solution in Javascript Try on Compiler
// Helper function to check if a square of given size is possible
var isPossible = function(prefixSum, threshold, size) {
var n = prefixSum.length;
var m = prefixSum[0].length;
// Iterate over all possible top-left corners of submatrices of given size
for (var i = 0; i + size <= n; i++) {
for (var j = 0; j + size <= m; j++) {
// Compute the sum of the current submatrix using the prefix sum matrix
var sum = prefixSum[i + size - 1][j + size - 1];
if (i > 0) sum -= prefixSum[i - 1][j + size - 1];
if (j > 0) sum -= prefixSum[i + size - 1][j - 1];
if (i > 0 && j > 0) sum += prefixSum[i - 1][j - 1];
// If sum is within threshold, return true
if (sum <= threshold) {
return true;
}
}
}
// Return false if no valid submatrix is found
return false;
};
// Function to find the maximum valid square size
var maxSideLength = function(mat, threshold) {
var n = mat.length;
var m = mat[0].length;
// Create a prefix sum matrix (0-based indexing, no extra row/column)
var prefixSum = new Array(n).fill(0).map(() => new Array(m).fill(0));
// Fill the prefix sum matrix
for (var i = 0; i < n; i++) {
for (var j = 0; j < m; j++) {
prefixSum[i][j] = mat[i][j];
if (i > 0) prefixSum[i][j] += prefixSum[i - 1][j];
if (j > 0) prefixSum[i][j] += prefixSum[i][j - 1];
if (i > 0 && j > 0) prefixSum[i][j] -= prefixSum[i - 1][j - 1];
}
}
// Initialize binary search range
var low = 1, high = Math.min(n, m), ans = 0;
// Iterate over all possible square sizes
for (var i = low; i <= high; i++) {
// Check if a square of size i is possible
if (isPossible(prefixSum, threshold, i)) {
ans = i;
}
}
// Return the maximum valid square size
return ans;
};
Complexity Analysis of Maximum Side Length of a Square with Sum Less than or Equal to Threshold(brute force):
Time Complexity: O(n × m × min(n, m))
Step 1: Prefix Sum Computation
- The first part of the algorithm constructs the prefix sum matrix, which involves iterating over all elements of the given matrix mat.
- Outer loop (rows) runs n times.
- Inner loop (columns) runs m times.
- Total operations = O(n × m).
Step 2: Checking Possible Square Sizes
- We iterate over possible square sizes from 0 to min(n, m) - 1, and for each size, we check if there exists a valid submatrix using the isPossible function.
- Binary search alternative is not used (since we are doing a linear check over size).
- The loop runs at most min(n, m) times.
- Each iteration calls isPossible, which checks all possible (n - size) × (m - size) submatrices.
Step 3: Checking if a Square of a Given Size is Possible (isPossible function)
- For each square size size, the function iterates over (n - size) × (m - size) submatrices.
- In the worst case (when size = min(n, m) - 1), this is approximately O(n × m) operations.
- Since we check min(n, m) different sizes, the worst-case total cost is O(n × m × min(n, m)).
Final Complexity
- Prefix sum computation: O(n × m)
- Checking all possible square sizes: O(n × m × min(n, m))
- Total Complexity: O(n × m × min(n, m))
Space Complexity: O(n × m)
- Auxiliary Space Complexity: O(n × m)
The algorithm constructs a prefix sum matrix of size n×m.
Space used: O(n × m). - Total Space Complexity: O(n × m)
The input mat already occupies O(n × m) space.
Therefore, the Total Space Complexity: O(n × m) + O(n × m) = O(n × m).
Will Brute Force Work Against the Given Constraints?
For the current solution, the time complexity is O(n × m × min(n, m)), where n and m are the dimensions of the matrix. The algorithm iterates over all possible square submatrices while checking their sums using prefix sums.
In the worst-case scenario, the algorithm iterates over all possible submatrix sizes from 1 to min(n, m) for each cell in the matrix, leading to a time complexity of O(n × m × min(n, m)).
This time complexity can become inefficient when n and m are large, particularly when both values are close to their upper bound (300). In such cases, the algorithm may perform a large number of operations (nearly 300 × 300 × 300 = 27 × 10⁶), making it computationally expensive.
This solution may not execute efficiently for all test cases, particularly when n and m are near their upper limits. While it may work for smaller matrices, it could exceed time limits for large inputs where n, m ≈ 300.
In competitive programming environments, the typical time complexity limit is around 10⁶ operations per test case. Therefore, for inputs with large n and m, this time complexity could lead to inefficient execution.
However, the solution is still able to pass on LeetCode due to less strict test cases, which do not include the most extreme edge cases.
How to optimize it?
In the previous approach, we checked every possible square size from 1 to min(n, m) and verified if it was possible to construct a square whose sum is within the threshold. This gave us an O(n × m × min(n, m)) time complexity, which was too slow and caused TLE (Time Limit Exceeded).
Now, let’s think about improving this.
The main issue was that we checked every possible square size from 1 to min(n, m), which took a lot of time.
Can we make this part faster?
Yes! Here’s the hint:
We are searching for the maximum possible square side length that still satisfies all the constraints. We know this maximum lies between 1 (smallest possible square) and min(n, m) (largest possible square within matrix bounds).
Now that we know the two endpoints, 1 and min(n, m), let's make a few observations:
- The data structure is sorted:
The range of possible square sizes is naturally sorted from 1 to min(n, m). - The search space is monotonic:
- If a certain square size k × k allows us to construct a valid submatrix within the threshold, then any smaller size will also work.
- If a certain square size does not allow us to construct a valid submatrix, then any larger size will also fail.
- For the example mat = [[1,1,3,2,4,3,2], [1,1,3,2,4,3,2], [1,1,3,2,4,3,2]], threshold = 4, the algorithm will fail for k = 3 because the sum exceeds threshold. However, starting from k = 1, 2, it will succeed, and the search will find that the maximum valid square side length is 2.
- The middle element helps minimize or maximize the search space:
If we take the middle value of the current range and check if it works (i.e., can we construct a valid square under the given threshold), we can narrow the search space:
If it works, we move to the right half to find a larger valid square.
If it doesn’t work, we move to the left half to find a smaller valid square.
If we plot a graph with the possible values of k (side length of the square) on the x-axis and the corresponding sum of the submatrix on the y-axis, we observe the following pattern:
- Before reaching the maximum valid square size, we can successfully construct squares that satisfy all constraints.
- However, once k exceeds this maximum value, it becomes impossible to construct a valid square while keeping the sum within threshold.
Thus, maxSideLength represents the largest square size k × k that still satisfies all constraints. Once this number is found, constructing a valid square remains feasible for any size ≤ maxSideLength.
With these points in mind, it's clear that instead of linearly checking all possible values from 1 to min(n, m), we can take the middle value and continually reduce the search space.
Does this approach remind you of something you've seen before?
Yes! We are applying binary search here. By leveraging the sorted and monotonic properties of the range of square sizes, we efficiently narrow down the search space to find the maximum valid square size, instead of checking each value linearly.
Binary Search Algorithm for Maximum Side-Length of a Square
Binary search can help us quickly find the maximum possible square size while satisfying all constraints.
- Start by taking the middle value between low (1) and high (min(n, m)).
- If this mid value satisfies the condition that we can construct a valid k × k square under threshold, we store it as a potential answer and move the search to the right half, looking for a larger valid square.
- Otherwise, we move the search to the left half to find a smaller valid square.
- We continue this process as long as low ≤ high.
- Once the condition breaks, the stored answer is returned as the maximum side length of the square in the matrix.
By using binary search, we can cut the search space in half at each step, which makes the solution much faster and avoids the TLE issue.
Let us understand this with a video.
maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold-optimal-approach-animation
Let's understand with an example:
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
Step 1: Initialize Binary Search Variables
- low = 1, high = min(3, 7) = 3, ans = 0
Step 2: Binary Search Iterations
- mid = (1 + 3) / 2 = 2
- Check if there exists a 2×2 square with sum ≤ 4
- Possible square at (0,0):
[[1,1],
[1,1]] → Sum = 4 (Valid ) - Update ans = 2, Move right → low = 3
- mid = (3 + 3) / 2 = 3
- Check if there exists a 3×3 square with sum ≤ 4
- Sum of any 3×3 square ≥ 9 (Exceeds threshold )
- Move left → high = 2
Step 3: Termination Condition
- low > high, so return ans = 2
Final Output: 2
Maximum valid square side length is 2.
How to code it up:
Understand the Problem Statement
- Given an m × n matrix mat and an integer threshold, find the maximum side length of a square with sum ≤ threshold.
Use Prefix Sum for Efficient Sum Calculation
- Construct a prefix sum matrix prefixSum to compute any submatrix sum in O(1) time.
Implement the Prefix Sum Matrix Construction
- Create an n × m matrix initialized to 0.
- Use the formula: prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1] + mat[i][j]
- Ensure proper boundary checks to avoid accessing negative indices.
Implement the isPossible() Function
- Iterate over all possible top-left corners.
- Compute the sum of the current square using the prefix sum formula.
- If any square of given size satisfies the threshold condition, return true.
Use Binary Search to Optimize the Solution
- Initialize low = 1 and high = min(n, m).
- Apply binary search on the square size:
- If a square of size mid is possible, move low up (mid + 1).
- If not, move high down (mid - 1).
- The largest valid mid is the answer.
Return the Maximum Valid Square Size
- The binary search finds the largest ans where a square of size ans satisfies the condition.
Maximum Side Length of a Square with Sum Less than or Equal to Threshold / Code Implementation
1. Maximum Side Length of a Square with Sum Less than or Equal to Threshold solution in c++ Try on Compiler
class Solution {
// Function to check if a square of given size has a sum ≤ threshold
bool isPossible(vector<vector<int>>& prefixSum, int threshold, int size) {
// Get matrix dimensions
int n = prefixSum.size();
int m = prefixSum[0].size();
// Iterate over all possible top-left corners of the square
for (int i = 0; i + size <= n; i++) {
for (int j = 0; j + size <= m; j++) {
// Calculate the sum of the current square using prefix sum matrix
int sum = prefixSum[i + size - 1][j + size - 1];
// Subtract the extra rows if applicable
if (i > 0) sum -= prefixSum[i - 1][j + size - 1];
// Subtract the extra columns if applicable
if (j > 0) sum -= prefixSum[i + size - 1][j - 1];
// Add back the overlapping top-left area
if (i > 0 && j > 0) sum += prefixSum[i - 1][j - 1];
// If the sum is within threshold, return true
if (sum <= threshold)
return true;
}
}
// Return false if no valid square is found
return false;
}
public:
// Function to find the largest square with sum ≤ threshold
int maxSideLength(vector<vector<int>>& mat, int threshold) {
// Get matrix dimensions
int n = mat.size();
int m = mat[0].size();
// Create prefix sum matrix of the same size as input matrix
vector<vector<int>> prefixSum(n, vector<int>(m, 0));
// Compute the prefix sum matrix
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
// Initialize with the current element value
prefixSum[i][j] = mat[i][j];
// Add the value from the top if not in the first row
if (i > 0) prefixSum[i][j] += prefixSum[i - 1][j];
// Add the value from the left if not in the first column
if (j > 0) prefixSum[i][j] += prefixSum[i][j - 1];
// Subtract the overlapping top-left area to avoid double counting
if (i > 0 && j > 0) prefixSum[i][j] -= prefixSum[i - 1][j - 1];
}
}
// Initialize binary search variables
int low = 1, high = min(n, m), ans = 0;
// Perform binary search to find the largest valid square size
while(low <= high) {
// Compute the middle size
int mid = (low + high) / 2;
// Check if a square of size 'mid' is possible
if(isPossible(prefixSum, threshold, mid)) {
// Update answer and search for a larger size
ans = mid;
low = mid + 1;
} else {
// Search for a smaller size
high = mid - 1;
}
}
// Return the maximum valid square size found
return ans;
}
};
2. Maximum Side Length of a Square with Sum Less than or Equal to Threshold solution in Java Try on Compiler
class Solution {
// Function to check if a square of given size has a sum ≤ threshold
private boolean isPossible(int[][] prefixSum, int threshold, int size) {
// Get matrix dimensions
int n = prefixSum.length;
int m = prefixSum[0].length;
// Iterate over all possible top-left corners of the square
for (int i = 0; i + size <= n; i++) {
for (int j = 0; j + size <= m; j++) {
// Calculate the sum of the current square using prefix sum matrix
int sum = prefixSum[i + size - 1][j + size - 1];
// Subtract the extra rows if applicable
if (i > 0) sum -= prefixSum[i - 1][j + size - 1];
// Subtract the extra columns if applicable
if (j > 0) sum -= prefixSum[i + size - 1][j - 1];
// Add back the overlapping top-left area
if (i > 0 && j > 0) sum += prefixSum[i - 1][j - 1];
// If the sum is within threshold, return true
if (sum <= threshold)
return true;
}
}
// Return false if no valid square is found
return false;
}
// Function to find the largest square with sum ≤ threshold
public int maxSideLength(int[][] mat, int threshold) {
// Get matrix dimensions
int n = mat.length;
int m = mat[0].length;
// Create prefix sum matrix
int[][] prefixSum = new int[n][m];
// Compute the prefix sum matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// Initialize with the current element value
prefixSum[i][j] = mat[i][j];
// Add the value from the top if not in the first row
if (i > 0) prefixSum[i][j] += prefixSum[i - 1][j];
// Add the value from the left if not in the first column
if (j > 0) prefixSum[i][j] += prefixSum[i][j - 1];
// Subtract the overlapping top-left area to avoid double counting
if (i > 0 && j > 0) prefixSum[i][j] -= prefixSum[i - 1][j - 1];
}
}
// Initialize binary search variables
int low = 1, high = Math.min(n, m), ans = 0;
// Perform binary search to find the largest valid square size
while (low <= high) {
// Compute the middle size
int mid = (low + high) / 2;
// Check if a square of size 'mid' is possible
if (isPossible(prefixSum, threshold, mid)) {
// Update answer and search for a larger size
ans = mid;
low = mid + 1;
} else {
// Search for a smaller size
high = mid - 1;
}
}
// Return the maximum valid square size found
return ans;
}
}
3. Maximum Side Length of a Square with Sum Less than or Equal to Threshold solution in Python Try on Compiler
class Solution:
# Function to check if a square of given size has a sum ≤ threshold
def isPossible(self, prefixSum, threshold, size):
# Get matrix dimensions
n = len(prefixSum)
m = len(prefixSum[0])
# Iterate over all possible top-left corners of the square
for i in range(n - size + 1):
for j in range(m - size + 1):
# Calculate the sum of the current square using prefix sum matrix
sum_val = prefixSum[i + size - 1][j + size - 1]
# Subtract the extra rows if applicable
if i > 0:
sum_val -= prefixSum[i - 1][j + size - 1]
# Subtract the extra columns if applicable
if j > 0:
sum_val -= prefixSum[i + size - 1][j - 1]
# Add back the overlapping top-left area
if i > 0 and j > 0:
sum_val += prefixSum[i - 1][j - 1]
# If the sum is within the threshold, return True
if sum_val <= threshold:
return True
# Return False if no valid square is found
return False
# Function to find the largest square with sum ≤ threshold
def maxSideLength(self, mat, threshold):
# Get matrix dimensions
n = len(mat)
m = len(mat[0])
# Create a prefix sum matrix of the same size as the input matrix
prefixSum = [[0] * m for _ in range(n)]
# Compute the prefix sum matrix
for i in range(n):
for j in range(m):
# Initialize with the current element value
prefixSum[i][j] = mat[i][j]
# Add the value from the top if not in the first row
if i > 0:
prefixSum[i][j] += prefixSum[i - 1][j]
# Add the value from the left if not in the first column
if j > 0:
prefixSum[i][j] += prefixSum[i][j - 1]
# Subtract the overlapping top-left area to avoid double counting
if i > 0 and j > 0:
prefixSum[i][j] -= prefixSum[i - 1][j - 1]
# Initialize binary search variables
low, high, ans = 1, min(n, m), 0
# Perform binary search to find the largest valid square size
while low <= high:
# Compute the middle size
mid = (low + high) // 2
# Check if a square of size 'mid' is possible
if self.isPossible(prefixSum, threshold, mid):
# Update answer and search for a larger size
ans = mid
low = mid + 1
else:
# Search for a smaller size
high = mid - 1
# Return the maximum valid square size found
return ans
4. Maximum Side Length of a Square with Sum Less than or Equal to Threshold solution in Javascript Try on Compiler
// Helper function to check if a square of given size is possible
var isPossible = function (prefixSum, threshold, size) {
var n = prefixSum.length;
var m = prefixSum[0].length;
// Iterate over all possible top-left corners of submatrices of given size
for (var i = 0; i + size <= n; i++) {
for (var j = 0; j + size <= m; j++) {
// Compute the sum of the current submatrix using the prefix sum matrix
var sum = prefixSum[i + size - 1][j + size - 1];
if (i > 0) sum -= prefixSum[i - 1][j + size - 1];
if (j > 0) sum -= prefixSum[i + size - 1][j - 1];
if (i > 0 && j > 0) sum += prefixSum[i - 1][j - 1];
// If sum is within threshold, return true
if (sum <= threshold) {
return true;
}
}
}
// Return false if no valid submatrix is found
return false;
};
// Function to find the maximum valid square size
var maxSideLength = function (mat, threshold) {
// Get matrix dimensions
let n = mat.length;
let m = mat[0].length;
// Create a prefix sum matrix of the same size as the input matrix
let prefixSum = new Array(n).fill(0).map(() => new Array(m).fill(0));
// Compute the prefix sum matrix
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
// Initialize with the current element value
prefixSum[i][j] = mat[i][j];
// Add the value from the top if not in the first row
if (i > 0) prefixSum[i][j] += prefixSum[i - 1][j];
// Add the value from the left if not in the first column
if (j > 0) prefixSum[i][j] += prefixSum[i][j - 1];
// Subtract the overlapping top-left area to avoid double counting
if (i > 0 && j > 0) prefixSum[i][j] -= prefixSum[i - 1][j - 1];
}
}
// Initialize binary search variables
let low = 1, high = Math.min(n, m), ans = 0;
// Perform binary search to find the largest valid square size
while (low <= high) {
// Compute the middle size
let mid = Math.floor((low + high) / 2);
// Check if a square of size 'mid' is possible
if (isPossible(prefixSum, threshold, mid)) {
// Update answer and search for a larger size
ans = mid;
low = mid + 1;
} else {
// Search for a smaller size
high = mid - 1;
}
}
// Return the maximum valid square size found
return ans;
};
Complexity Analysis of Maximum Side Length of a Square with Sum Less than or Equal to Threshold(binary search):
Time Complexity : O(n × m × log(min(n, m)))
The given algorithm consists of two main parts:
- Precomputing the Prefix Sum Matrix
- Binary Search to Find the Maximum Valid Square Side Length
Let's analyze each part separately.
- Precomputing the Prefix Sum Matrix
- We iterate over all n × m elements of the matrix mat to construct the prefix sum matrix.
- The computation for each element takes O(1) time.
- Total Time Complexity: O(n × m)
- Binary Search on Side Length
- The possible side lengths of the square range from 0 to min(n, m) - 1.
- Thus, the binary search runs in O(log(min(n, m))) time.
- Checking If a Square of Size mid is Possible
- For each mid, we iterate over all possible (n - mid) × (m - mid) positions in the matrix.
- This is roughly O(n × m) in the worst case.
- Since binary search performs O(log(min(n, m))) iterations and each iteration requires O(n × m) checks using the prefix sum matrix,
the total complexity of this step is O(n × m × log(min(n, m))).
Final Time Complexity
- Preprocessing: O(n × m)
- Binary Search: O(n × m × log(min(n, m)))
- Final Complexity: O(n × m × log(min(n, m)))
Thus, the overall time complexity of the solution remains: O(n × m × log(min(n, m)))
Space Complexity : O(n × m)
- Auxiliary Space Complexity: O(n × m)
The algorithm constructs a prefix sum matrix of size n×m.
Space used: O(n × m). - Total Space Complexity: O(n × m)
The input mat already occupies O(n × m) space.
Therefore, the Total Space Complexity: O(n × m) + O(n × m) = O(n × m).
Similar Problems
Finding the maximum sum square submatrix with a sum less than or equal to k is a common challenge in coding platforms like LeetCode. This problem, often referred to as the maximum sum submatrix or largest subgrid problem, requires efficient techniques to identify the optimal submatrix. By leveraging methods like prefix sums, binary search, and dynamic programming, you can efficiently solve this problem while ensuring optimal performance. Mastering this concept is crucial for improving problem-solving skills in competitive programming and technical interviews.
Now we have successfully tackled this problem, let's try these similar problems.
You are given an n x n integer matrix. You can do the following operation any number of times:
- Choose any two adjacent elements of matrix and multiply each of them by -1.
Two elements are considered adjacent if and only if they share a border.
Your goal is to maximize the summation of the matrix's elements. Return the maximum sum of the matrix's elements using the operation mentioned above.
Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.