We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

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

Number: 1413

Difficulty: Medium

Paid? No

Companies: IMC, Google

Problem Description

Given an m x n matrix mat and an integer threshold, return the maximum side-length of any square submatrix such that the sum of its elements is less than or equal to threshold. If no such square exists, return 0.

Key Insights

  • Use a 2D prefix sum to compute the sum of any submatrix in constant time.
  • Use binary search on the possible side lengths (from 0 to min(m, n)) to find the maximum valid square.
  • For each candidate square size, iterate over all possible top-left positions and check the sum using the prefix sum.
  • Maintain efficiency under the constraints using combined binary search and prefix sum techniques.

Space and Time Complexity

Time Complexity: O(m * n * log(min(m, n)))
Space Complexity: O(m * n)

Solution

The solution first constructs a 2D prefix sum matrix where each cell (i, j) holds the cumulative sum from the start of the matrix to position (i-1, j-1). With this structure, the sum of any square submatrix can be calculated in O(1) time using the inclusion-exclusion principle. Binary search is then applied on the possible side lengths. For each candidate size, the algorithm checks all valid positions in the matrix. If any square of that side length has a sum less than or equal to the threshold, the candidate size is acceptable, and the search continues for larger sizes; otherwise, it searches for smaller sizes.

Code Solutions

# Python Solution
class Solution:
    def maxSideLength(self, mat, threshold):
        m, n = len(mat), len(mat[0])
        # Build prefix sum matrix with extra row and column
        prefixSum = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                prefixSum[i][j] = mat[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1]
        
        def canFindSquare(side):
            # Check if any square of size 'side' has sum <= threshold
            for i in range(side, m + 1):
                for j in range(side, n + 1):
                    currentSum = prefixSum[i][j] - prefixSum[i-side][j] - prefixSum[i][j-side] + prefixSum[i-side][j-side]
                    if currentSum <= threshold:
                        return True
            return False
        
        lo, hi, ans = 0, min(m, n), 0
        # Binary search for maximum valid square size
        while lo <= hi:
            mid = (lo + hi) // 2
            if canFindSquare(mid):
                ans = mid
                lo = mid + 1
            else:
                hi = mid - 1
        return ans
← Back to All Questions