2943. Maximize Area of Square Hole in Grid

Array
Sorting
Greedy

TIME

O(h log h + v log v)

SPACE

O(1)

Intuition

To maximize the square hole area, we need to find the maximum gap we can create by removing consecutive bars in both horizontal and vertical directions. The key insight is that removing consecutive bars creates a larger gap than removing scattered bars.

Solution

Find maximum consecutive sequence: For both hBars and vBars, find the longest sequence of consecutive removable bars.
Calculate gap size: If we remove k consecutive bars, the resulting gap spans k + 1 unit cells (the space between the bars before and after the removed section).
Square constraint: The side of the square is limited by the smaller of the two maximum gaps (horizontal and vertical).
Return area: Square the side length to get the maximum area.

Algorithm

Sort both arrays
Find longest consecutive run in each array
Gap size = longest consecutive run + 1
Side = min(horizontal gap, vertical gap)
Area = side²

Complexity

Time: O(h log h + v log v) where h = len(hBars), v = len(vBars), dominated by sorting
Space: O(1), only using constant extra space (excluding input sort)

Edge Cases

Single bar in hBars or vBars → gap is 2 (1 bar removed + 1)
No consecutive bars → gap is 2 for each removed bar
All bars consecutive → maximum possible gap

Code

class Solution:
    def maximizeSquareHoleArea(self, n: int, m: int, hBars: list[int], vBars: list[int]) -> int:
        """
        2943. Maximize Area of Square Hole in Grid
        Time: O(h log h + v log v)
        Space: O(1)
        """
        def max_gap(arr: list[int]) -> int:
            arr.sort()
            longest = 1
            curr = 1
            
            for i in range(1, len(arr)):
                if arr[i] == arr[i - 1] + 1:
                    curr += 1
                else:
                    longest = max(longest, curr)
                    curr = 1
            
            longest = max(longest, curr)
            return longest + 1
        
        max_h = max_gap(hBars)
        max_v = max_gap(vBars)
        
        side = min(max_h, max_v)
        return side * side

import java.util.Arrays;

/**
 * 2943. Maximize Area of Square Hole in Grid
 * Time: O(h log h + v log v)
 * Space: O(1)
 */
class Solution {
    public int maximizeSquareHoleArea(int n, int m, int[] hBars, int[] vBars) {
        int maxH = maxGap(hBars);
        int maxV = maxGap(vBars);
        
        int side = Math.min(maxH, maxV);
        return side * side;
    }
    
    private int maxGap(int[] arr) {
        Arrays.sort(arr);
        
        int longest = 1;
        int curr = 1;
        
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] == arr[i - 1] + 1) {
                curr++;
            } else {
                longest = Math.max(longest, curr);
                curr = 1;
            }
        }
        
        longest = Math.max(longest, curr);
        return longest + 1;
    }
}