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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

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

Difficulty: Medium

Problem Description

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.

Key Insights

  • We need to find the largest square submatrix where the sum of its elements is less than or equal to a given threshold.
  • A brute force approach would involve checking every possible square, which may be inefficient for larger matrices.
  • Utilizing a prefix sum array can help calculate the sum of any submatrix in constant time, significantly improving efficiency.
  • Binary search can be applied on the possible side lengths of the square to find the maximum valid side length efficiently.

Space and Time Complexity

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

Solution

To solve the problem, we use the following approach:

  1. Prefix Sum Array: First, we create a prefix sum array to quickly compute the sum of any rectangular submatrix.
  2. Binary Search: We can employ binary search to find the maximum side length of the square. For each candidate side length, we check all possible positions for the top-left corner of the square and see if the sum of that square is within the threshold using the prefix sum array.

Code Solutions

def maxSideLength(mat, threshold):
    m, n = len(mat), len(mat[0])
    # Step 1: Create prefix sum array
    prefix_sum = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            prefix_sum[i][j] = mat[i - 1][j - 1] + prefix_sum[i - 1][j] + prefix_sum[i][j - 1] - prefix_sum[i - 1][j - 1]
    
    def sumSquare(x1, y1, size):
        x2, y2 = x1 + size, y1 + size
        return prefix_sum[x2][y2] - prefix_sum[x1][y2] - prefix_sum[x2][y1] + prefix_sum[x1][y1]
    
    # Step 2: Binary search
    left, right, max_side = 1, min(m, n), 0
    
    while left <= right:
        mid = (left + right) // 2
        found = False
        
        for i in range(m - mid + 1):
            for j in range(n - mid + 1):
                if sumSquare(i, j, mid) <= threshold:
                    found = True
                    break
            if found:
                break
        
        if found:
            max_side = mid
            left = mid + 1
        else:
            right = mid - 1
    
    return max_side
← Back to All Questions