1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold
Problem Description
Given a matrix of integers mat with dimensions m x n and an integer threshold, the task is to find the maximum side length of a square submatrix where the sum of its elements is less than or equal to threshold. If no such square exists, we should return 0. The problem challenges us to do this efficiently across all possible submatrices in a large matrix.
Intuition
To solve this problem, we use dynamic programming to precompute the sums of submatrices to quickly assess whether a square of a given size meets the threshold criteria. The intuition behind the approach is to use a binary search algorithm to efficiently find the maximum side length, combined with a sum lookup that leverages the precomputed sums of submatrices.
First, we create an auxiliary matrix s where each element s[i][j] represents the sum of elements in the rectangle from the top-left corner of the matrix to (i, j). This auxiliary matrix allows us to compute the sum of any submatrix in constant time by using the inclusion-exclusion principle.
The binary search is done on the side length of the square. For each possible side length k, we use the auxiliary matrix to check if there exists at least one square submatrix of size k x k with a sum less than or equal to threshold. If such a square exists for a side length k, we know that any smaller square will also satisfy the condition, so we continue the search for larger squares. If there is no such square, we decrease the side length and continue the search. This process is repeated until we narrow down to the maximum square size that satisfies the sum condition.
By combining binary search for efficiency and dynamic programming for fast submatrix sum calculation, the algorithm efficiently solves the problem without checking every possible square individually, which would be computationally expensive.
Learn more about Binary Search and Prefix Sum patterns.
What data structure does Breadth-first search typically uses to store intermediate states?
Solution Approach
The provided solution leverages dynamic programming and binary search to find the maximum side-length of a square with a sum less than or equal to the provided threshold.
Dynamic Programming
To calculate the sum of any submatrix quickly, an auxiliary matrix s is created. This 2D array stores the cumulative sum for every index (i, j) representing the sum of elements from (0, 0) to (i, j).
The sum for each element s[i][j] is obtained by:
1s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + mat[i - 1][j - 1]
This formulation is based on the inclusion-exclusion principle, where s[i - 1][j] + s[i][j - 1] adds the rectangle above and to the left of (i, j), but since the intersection (mat[0][0] to mat[i - 1][j - 1]) is added twice, it is subtracted once with - s[i - 1][j - 1]. Finally, mat[i - 1][j - 1] is added to include the current cell.
Binary Search
Binary search is used to find the maximum valid square side length. The search range is from 0 to the minimum of the matrix's height and width, as this represents the largest potential square.
Within each iteration of binary search:
- The middle of the current range (
mid) is selected as the candidate side-length for the square. - A check function,
check(k), is called to verify if there exists at least onek x ksquare whose sum is withinthreshold. - If such a square exists for
mid, the lower half (l) of the search is updated tomid, as we want to continue searching for possibly larger squares that satisfy the condition. - If no such square exists for
mid, the upper half (r) is updated tomid - 1. - The binary search loop continues until
lis no longer less thanr.
The check(k) function iterates over all possible positions for the top-left corner of a k x k square. It uses the previously computed auxiliary matrix s to determine if the sum of the square is less than or equal to threshold by performing a simple subtraction operation that removes the unnecessary areas, similar to how s was populated.
1v = s[i + k][j + k] - s[i][j + k] - s[i + k][j] + s[i][j]
Time Complexity
The overall time complexity of the solution is O(m * n * log(min(m, n))), where m and n are the dimensions of the input matrix. This is due to the binary search varying between 1 and min(m, n) and the sum check performed within the check(k) function that takes O(m * n) time.
As a result, the solution is efficient and effective, providing a fast way to compute the largest square within threshold while avoiding the overhead of calculating every possible square sum independently.
Which algorithm should you use to find a node that is close to the root of the tree?
Example Walkthrough
Let's illustrate the solution approach using a small example. Suppose we have the following 3x3 matrix mat and a threshold of 8:
1mat = [ 2 [1, 2, 3], 3 [4, 5, 6], 4 [7, 8, 9] 5]
We want to find the maximum side length of a square submatrix where the sum of its elements is less than or equal to threshold.
First, we build the auxiliary matrix s to store cumulative sums:
1s = [ 2 [0, 0, 0, 0], 3 [0, 1, 3, 6], 4 [0, 5, 12, 21], 5 [0, 12, 27, 45] 6]
Each element s[i][j] represents the sum of elements from (0, 0) to (i-1, j-1) in the original matrix.
Next, we use binary search to find the maximum side length of the square. We start the search with left = 0 and right = min(m, n) = 3.
- The first
midvalue is(0 + 3) / 2 = 1.5, rounded down to1. - We call
check(1)for each possible1x1square and see if any square's sum is less than or equal to the threshold. For1x1squares, all values from the original matrix qualify, as they are all less than8. - Since
check(1)is true, we updateleft = mid + 1, and the new range becomes2to3.
We repeat this process:
- Our next
midis(2 + 3) / 2 = 2.5, rounded down to2. - We call
check(2)for each possible2x2square. For instance, for the top-left2x2square:- Calculate its sum using the auxiliary matrix
s:s[2][2] - s[0][2] - s[2][0] + s[0][0] = 12 - 0 - 0 + 0 = 12, which is greater than the threshold. - Hence, no
2x2square has a sum less than or equal to the threshold.
- Calculate its sum using the auxiliary matrix
- Since
check(2)is false, we updateright = mid - 1, and the range becomes2to1.
Since left is not less than right, the binary search terminates, and we find that the maximum side length of a square submatrix with a sum less than or equal to the threshold is 1.
Solution Implementation
1from typing import List
2
3class Solution:
4 def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
5 # Define a function to check if a square with side k fits the threshold
6 def check_square_fits(k: int) -> bool:
7 for i in range(rows - k + 1):
8 for j in range(cols - k + 1):
9 # Compute the sum of the square using prefix sum technique
10 square_sum = prefix_sum[i + k][j + k] - prefix_sum[i][j + k] - prefix_sum[i + k][j] + prefix_sum[i][j]
11 # If the sum is within the threshold, then square of side k fits
12 if square_sum <= threshold:
13 return True
14 return False
15
16 # Matrix dimensions
17 rows, cols = len(mat), len(mat[0])
18
19 # Calculate the prefix sum matrix for efficient area sum calculation
20 # Padding with an extra row and column filled with 0 for easy calculation
21 prefix_sum = [[0] * (cols + 1) for _ in range(rows + 1)]
22 for i in range(1, rows + 1):
23 for j in range(1, cols + 1):
24 prefix_sum[i][j] = prefix_sum[i - 1][j] + prefix_sum[i][j - 1] - prefix_sum[i - 1][j - 1] + mat[i - 1][j - 1]
25
26 # Initialize binary search bounds
27 left, right = 0, min(rows, cols)
28
29 # Perform binary search to find the maximum square side length
30 while left < right:
31 mid = (left + right + 1) // 2 # Use integer division for Python 3
32 # Check if there's a square with the current mid side length that fits the threshold
33 if check_square_fits(mid):
34 left = mid
35 else:
36 right = mid - 1
37
38 # The left pointer now points to the maximum size square that fits the threshold
39 return left
401class Solution {
2 private int numRows; // Number of rows in the matrix
3 private int numCols; // Number of columns in the matrix
4 private int threshold; // Threshold for the maximum sum of the square sub-matrix
5 private int[][] prefixSum; // Prefix sum matrix
6
7 public int maxSideLength(int[][] mat, int threshold) {
8 this.numRows = mat.length;
9 this.numCols = mat[0].length;
10 this.threshold = threshold;
11 this.prefixSum = new int[numRows + 1][numCols + 1];
12
13 // Build the prefix sum matrix
14 for (int i = 1; i <= numRows; ++i) {
15 for (int j = 1; j <= numCols; ++j) {
16 prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1]
17 - prefixSum[i - 1][j - 1] + mat[i - 1][j - 1];
18 }
19 }
20
21 int left = 0, right = Math.min(numRows, numCols);
22 // Binary search for the maximum side length of a square sub-matrix
23 while (left < right) {
24 int mid = (left + right + 1) >> 1;
25 if (canFindSquareWithMaxSum(mid)) {
26 left = mid;
27 } else {
28 right = mid - 1;
29 }
30 }
31 return left;
32 }
33
34 // Check if there's a square sub-matrix of side length k with a sum less than or equal to the threshold
35 private boolean canFindSquareWithMaxSum(int sideLength) {
36 for (int i = 0; i <= numRows - sideLength; ++i) {
37 for (int j = 0; j <= numCols - sideLength; ++j) {
38 int sum = prefixSum[i + sideLength][j + sideLength]
39 - prefixSum[i][j + sideLength]
40 - prefixSum[i + sideLength][j] + prefixSum[i][j];
41 if (sum <= threshold) {
42 return true;
43 }
44 }
45 }
46 return false;
47 }
48}
491#include <vector>
2#include <cstring>
3
4class Solution {
5public:
6 int maxSideLength(vector<vector<int>>& matrix, int threshold) {
7 int rows = matrix.size();
8 int cols = matrix[0].size();
9
10 // Prefix sum array with extra row and column to handle boundary conditions.
11 int prefixSum[rows + 1][cols + 1];
12 memset(prefixSum, 0, sizeof(prefixSum));
13
14 // Calculate prefix sum for the matrix.
15 for (int i = 1; i <= rows; ++i) {
16 for (int j = 1; j <= cols; ++j) {
17 prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + matrix[i - 1][j - 1];
18 }
19 }
20
21 // Lambda function that checks if there's a square with side length k
22 // that has a sum less than or equal to the threshold.
23 auto isSquareValid = [&](int k) {
24 for (int i = 0; i <= rows - k; ++i) {
25 for (int j = 0; j <= cols - k; ++j) {
26 // Calculate the sum for the current square.
27 int squareSum = prefixSum[i + k][j + k] - prefixSum[i][j + k] -
28 prefixSum[i + k][j] + prefixSum[i][j];
29
30 if (squareSum <= threshold) {
31 return true;
32 }
33 }
34 }
35 return false;
36 };
37
38 // Binary search to find the maximum valid side length.
39 int left = 0, right = min(rows, cols);
40 while (left < right) {
41 // Midpoint of the current search range, rounding up.
42 int mid = (left + right + 1) / 2;
43 if (isSquareValid(mid)) {
44 left = mid; // Mid is possible, search higher.
45 } else {
46 right = mid - 1; // Mid is too large, search lower.
47 }
48 }
49
50 return left; // Left will contain the maximum valid side length.
51 }
52};
531function maxSideLength(mat: number[][], threshold: number): number {
2 const rows = mat.length; // Total number of rows in the matrix
3 const cols = mat[0].length; // Total number of columns in the matrix
4 const prefixSum: number[][] = Array.from({ length: rows + 1 }, () => Array(cols + 1).fill(0)); // Initialize prefix sum matrix
5
6 // Compute the prefix sum of the matrix
7 for (let i = 1; i <= rows; ++i) {
8 for (let j = 1; j <= cols; ++j) {
9 prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + mat[i - 1][j - 1];
10 }
11 }
12
13 // Check function to verify if there exists a square with side length k whose sum is below the threshold
14 const hasValidSquare = (k: number): boolean => {
15 for (let i = 0; i <= rows - k; ++i) {
16 for (let j = 0; j <= cols - k; ++j) {
17 const sum = prefixSum[i + k][j + k] - prefixSum[i + k][j] - prefixSum[i][j + k] + prefixSum[i][j];
18 if (sum <= threshold) {
19 return true; // Found valid square
20 }
21 }
22 }
23 return false; // No valid square found
24 };
25
26 let left = 0; // Lower bound of the side length search space
27 let right = Math.min(rows, cols); // Upper bound of the side length search space
28
29 // Binary search to find the maximum side length of a square with a sum less than or equal to the threshold
30 while (left < right) {
31 const mid = Math.floor((left + right + 1) / 2); // Mid-point of the current search space
32 if (hasValidSquare(mid)) {
33 left = mid; // The square side length can be at least 'mid', continue searching right
34 } else {
35 right = mid - 1; // 'mid' is too large, continue searching left
36 }
37 }
38
39 return left; // The largest valid side length found
40}
41Which data structure is used to implement priority queue?
Time and Space Complexity
Time Complexity
The provided code operates in several steps. The computation of the prefix sum matrix, s, takes O(m * n) time where m is the number of rows and n is the number of columns in the input matrix, mat. This is because it needs to iterate over every element in mat to compute the sum.
The check function, which checks if a square with side k has a sum less than or equal to the threshold, is O(m * n) as well for each individual k, since, in the worst case, it has to iterate over the entire matrix again, checking each possible top-left corner of a square.
Finally, the binary search performed in the last part of the code runs in O(log(min(m, n))) time. Since the binary search calls the check function at each iteration, the combined time complexity for the search routine with subsequent checks is O(m * n * log(min(m, n))).
Hence, the overall time complexity of the code is O(m * n + m * n * log(min(m, n))) which simplifies to O(m * n * log(min(m, n))).
Space Complexity
Regarding space complexity, the additional space is used for the prefix sum matrix, s, which has dimensions (m + 1) x (n + 1). Therefore, the space complexity is O((m + 1) * (n + 1)), which simplifies to O(m * n) since the +1 is relatively negligible for large m and n.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of these pictures shows the visit order of a depth-first search?
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.