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 Square Area by Removing Fences From a Field

Difficulty: Medium

Problem Description

There is a large (m - 1) x (n - 1) rectangular field with corners at (1, 1) and (m, n) containing some horizontal and vertical fences given in arrays hFences and vFences respectively. Horizontal fences are from the coordinates (hFences[i], 1) to (hFences[i], n) and vertical fences are from the coordinates (1, vFences[i]) to (m, vFences[i]). Return the maximum area of a square field that can be formed by removing some fences (possibly none) or -1 if it is impossible to make a square field. Since the answer may be large, return it modulo 10^9 + 7.

Key Insights

  • The field is bounded by the outer fences that cannot be removed.
  • The maximum square area that can be formed is determined by the largest gaps between fences in both horizontal and vertical directions.
  • The area of the square is limited by the smaller dimension of the largest free gap in rows and columns.
  • If there are no possible gaps for forming a square, return -1.

Space and Time Complexity

Time Complexity: O(h + v), where h is the number of horizontal fences and v is the number of vertical fences, since we need to analyze the gaps created by these fences. Space Complexity: O(1), as we are only using a constant amount of extra space for calculations.

Solution

To solve the problem, we will:

  1. Sort the horizontal and vertical fences to easily calculate the gaps between them.
  2. Calculate the maximum gap between consecutive horizontal fences and between consecutive vertical fences.
  3. The side length of the largest square that can be formed is the minimum of the largest horizontal gap and the largest vertical gap.
  4. Return the square of that side length as the area, modulo 10^9 + 7. If no square can be formed, return -1.

Code Solutions

def maxSquareArea(m: int, n: int, hFences: List[int], vFences: List[int]) -> int:
    MOD = 10**9 + 7
    
    # Add boundary fences
    hFences = [0] + sorted(hFences) + [m]
    vFences = [0] + sorted(vFences) + [n]
    
    # Find the maximum gap for horizontal fences
    max_h_gap = max(hFences[i] - hFences[i - 1] for i in range(1, len(hFences)))
    
    # Find the maximum gap for vertical fences
    max_v_gap = max(vFences[i] - vFences[i - 1] for i in range(1, len(vFences)))
    
    # The largest square side length is the minimum of both gaps
    square_side = min(max_h_gap, max_v_gap) - 1
    
    return (square_side ** 2) % MOD if square_side > 0 else -1
← Back to All Questions