Problem Statement in English

You’re given two integer arrays hBars and vBars representing the positions of horizontal and vertical bars in a grid.

The bars divide the grid into smaller sections.

Your task is to find the maximum area of a square hole that can be formed in the grid without being obstructed by any bars.

Approach

What’s crucial here is that you figure out that no matter where the horizontal bar is, it’ll always cut through the entire width of the grid, thus merging with vertical sections that have been cut.

Once you realize that, the problem simplifies to finding the longest consecutive sequence of horizontal and vertical bars.

The maximum square hole area will be determined by the smaller of these two lengths, since the sides have to be equal.

Solution in Python


class Solution:
    def maximizeSquareHoleArea(self, n: int, m: int, hBars: List[int], vBars: List[int]) -> int:
        hBars.sort()
        vBars.sort()

        def streak(bars):
            if not bars:
                return 0

            best = current = 1

            for i in range(1, len(bars)):
                if bars[i - 1] + 1 == bars[i]:
                    current += 1
                else:
                    current = 1
                best = max(best, current)
            return best
        
        v = streak(vBars)
        h = streak(hBars)

        return (min(v, h) + 1) ** 2

Complexity

  • Time: $O(n \log n + m \log m)$
    Since we sort both the horizontal and vertical bars, the time complexity is dominated by the sorting step.

  • Space: $O(1)$
    Since we are using only a constant amount of extra space.

Mistakes I Made

I had to look this up :(

And we are done.