{x}
blog image

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

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.length
  • n == mat[i].length
  • 1 <= m, n <= 300
  • 0 <= mat[i][j] <= 104
  • 0 <= threshold <= 105

Solution Explanation

This problem asks to find the maximum side length of a square within a given matrix where the sum of the elements within the square is less than or equal to a given threshold. The solution uses a combination of prefix sum and binary search for an efficient approach.

1. Prefix Sum:

The core idea is to efficiently calculate the sum of elements within any square submatrix. We achieve this using a prefix sum array s. s[i][j] stores the sum of all elements in the submatrix from (0, 0) to (i-1, j-1). This allows us to calculate the sum of any arbitrary rectangular submatrix in O(1) time using the formula:

sum(submatrix from (r1, c1) to (r2, c2)) = s[r2+1][c2+1] - s[r1][c2+1] - s[r2+1][c1] + s[r1][c1]

2. Binary Search:

Once we have the prefix sum array, we can use binary search to efficiently find the maximum side length. The binary search iterates through possible side lengths, checking if a square of that side length exists with a sum less than or equal to the threshold.

The check(k) function in the code verifies if a square of side length k exists that meets the threshold condition. It iterates through all possible positions of such squares and uses the prefix sum to calculate the sum efficiently.

3. Algorithm:

  1. Prefix Sum Calculation: Build the prefix sum array s.
  2. Binary Search: Use binary search to find the maximum side length.
    • The search space is from 0 to min(m, n), where m and n are the dimensions of the matrix.
    • For each mid (potential side length), use check(mid) to determine if a square of that size exists that satisfies the condition.
    • If check(mid) is true, it means a square with side length mid exists, so we update l = mid (searching for larger squares).
    • Otherwise, we update r = mid - 1 (searching for smaller squares).
  3. Return: After the binary search, l will hold the maximum side length.

Time Complexity Analysis:

  • Prefix Sum: Calculating the prefix sum array takes O(m*n) time, where 'm' and 'n' are the dimensions of the matrix.
  • Binary Search: The binary search takes O(min(m, n) * m * n) time in the worst case because check(k) takes O(mn) time for each side length 'k' and the binary search iterates log(min(m,n)) times. However, the dominant factor is the prefix sum calculation, making the overall time complexity O(mn).
  • Check Function: The check function iterates through possible square positions, which takes O(m*n) time in the worst case.

Therefore, the overall time complexity is O(m*n).

Space Complexity Analysis:

The space complexity is dominated by the prefix sum array s, which takes O(mn) space. Therefore, the space complexity is **O(mn)**.

The provided code in Python, Java, C++, Go, and TypeScript implements this algorithm. They all follow the same logic, differing only in syntax and specific language features. The comments within the code further clarify the steps.