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

Maximize Area of Square Hole in Grid

Number: 3214

Difficulty: Medium

Paid? No

Companies: Swiggy

Problem Description

Given a grid formed by n+2 horizontal and m+2 vertical bars, where removing some bars (specified in arrays hBars and vBars) creates gaps between fixed bars, determine the maximum area of a square-shaped hole that can be formed.

Key Insights

  • Add boundaries (i.e., the fixed bars at positions 1 and n+2 for horizontal, 1 and m+2 for vertical) to the respective arrays.
  • Sorting the provided hBars and vBars along with boundaries helps compute the maximum gap.
  • The gap between two fixed bars is defined as the difference minus one.
  • The side length of the maximum square hole is dictated by the smaller of the two maximum gaps (horizontal and vertical).
  • The final answer is the square of that side length.

Space and Time Complexity

Time Complexity: O(H log H + V log V), where H and V are the lengths of hBars and vBars. Space Complexity: O(1) extra space (assuming input arrays count as given).

Solution

The solution involves augmenting the input arrays with fixed grid boundaries and then sorting these arrays. The next step is to calculate the maximum gap between adjacent horizontal bars and vertical bars (subtracting one to account for bar positions). The maximum square hole is constrained by the smaller of these two maximum gaps, and its area is computed by squaring the side length. This approach uses sorting and simple array traversal to achieve the answer.

Code Solutions

# Python solution with line-by-line comments

def maximize_square_area(n, m, hBars, vBars):
    # Include fixed horizontal boundaries: 1 and n+2
    horizontal_bars = [1] + sorted(hBars) + [n + 2]
    # Include fixed vertical boundaries: 1 and m+2
    vertical_bars = [1] + sorted(vBars) + [m + 2]
    
    # Find maximum gap in horizontal bars
    max_h_gap = 0
    for i in range(1, len(horizontal_bars)):
        gap = horizontal_bars[i] - horizontal_bars[i - 1] - 1
        max_h_gap = max(max_h_gap, gap)
    
    # Find maximum gap in vertical bars
    max_v_gap = 0
    for i in range(1, len(vertical_bars)):
        gap = vertical_bars[i] - vertical_bars[i - 1] - 1
        max_v_gap = max(max_v_gap, gap)
    
    # The side of the square hole is the minimum of the two maximum gaps
    side = min(max_h_gap, max_v_gap)
    # Return the square of the side length as the area
    return side * side

# Example test cases:
print(maximize_square_area(2, 1, [2, 3], [2]))  # Expected output: 4
print(maximize_square_area(1, 1, [2], [2]))       # Expected output: 4
print(maximize_square_area(2, 3, [2, 3], [2, 4]))   # Expected output: 4
← Back to All Questions