1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold

MediumArrayBinary SearchMatrixPrefix Sum

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.

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:

s[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 one k x k square whose sum is within threshold.
If such a square exists for mid, the lower half (l) of the search is updated to mid, 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 to mid - 1.
The binary search loop continues until l is no longer less than r.

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.

v = 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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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:

mat = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]

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:

s = [
  [0, 0, 0, 0],
  [0, 1, 3, 6],
  [0, 5, 12, 21],
  [0, 12, 27, 45]
]

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 mid value is (0 + 3) / 2 = 1.5, rounded down to 1.
We call check(1) for each possible 1x1 square and see if any square's sum is less than or equal to the threshold. For 1x1 squares, all values from the original matrix qualify, as they are all less than 8.
Since check(1) is true, we update left = mid + 1, and the new range becomes 2 to 3.

We repeat this process:

Our next mid is (2 + 3) / 2 = 2.5, rounded down to 2.
We call check(2) for each possible 2x2 square. For instance, for the top-left 2x2 square:
- 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 2x2 square has a sum less than or equal to the threshold.
Since check(2) is false, we update right = mid - 1, and the range becomes 2 to 1.

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
40

1class 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}
49

1#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};
53

1function 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}
41

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What does the following code do?

1def f(arr1, arr2):
2  i, j = 0, 0
3  new_arr = []
4  while i < len(arr1) and j < len(arr2):
5      if arr1[i] < arr2[j]:
6          new_arr.append(arr1[i])
7          i += 1
8      else:
9          new_arr.append(arr2[j])
10          j += 1
11  new_arr.extend(arr1[i:])
12  new_arr.extend(arr2[j:])
13  return new_arr
14

1public static List<Integer> f(int[] arr1, int[] arr2) {
2  int i = 0, j = 0;
3  List<Integer> newArr = new ArrayList<>();
4
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.add(arr1[i]);
8          i++;
9      } else {
10          newArr.add(arr2[j]);
11          j++;
12      }
13  }
14
15  while (i < arr1.length) {
16      newArr.add(arr1[i]);
17      i++;
18  }
19
20  while (j < arr2.length) {
21      newArr.add(arr2[j]);
22      j++;
23  }
24
25  return newArr;
26}
27

1function f(arr1, arr2) {
2  let i = 0, j = 0;
3  let newArr = [];
4  
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.push(arr1[i]);
8          i++;
9      } else {
10          newArr.push(arr2[j]);
11          j++;
12      }
13  }
14  
15  while (i < arr1.length) {
16      newArr.push(arr1[i]);
17      i++;
18  }
19  
20  while (j < arr2.length) {
21      newArr.push(arr2[j]);
22      j++;
23  }
24  
25  return newArr;
26}
27

Find the intersection of two arrays.

Check if one array is a subsequence of the other.

Merge two sorted arrays.

Finding median values of 2 arrays.

I don’t know

1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold

Problem Description

Intuition

Solution Approach

Dynamic Programming

Binary Search

Time Complexity

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings