Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Removing a run of r consecutive bars joins r + 1 adjacent unit gaps. Bars separated by a bar that must remain cannot create one larger opening. A square therefore depends on the longest removable run in each direction, with its side limited by the smaller opening.

Approach

Sort the horizontal and vertical bar lists independently. In each list, scan consecutive values: extend the current run when the next bar index is exactly one larger, otherwise restart the run at one. Record the longest run in each direction.

If those run lengths are maxh and maxv, the available dimensions are maxh + 1 and maxv + 1. Choose side length min(maxh, maxv) + 1 and return its square. The two choices are independent, so the smaller dimension is both an upper bound and an achievable square side.

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

        maxh = 1 # max number of consecutive horizontal bars
        curr = 1
        for i in range(1, hb):
            if hBars[i - 1] + 1 == hBars[i]:
                curr += 1
            else:
                curr = 1
            maxh = max(maxh, curr)

        maxv = 1 # max number of consecutive vertical bars
        curr = 1
        for i in range(1, vb):
            if vBars[i - 1] + 1 == vBars[i]:
                curr += 1
            else:
                curr = 1
            maxv = max(maxv, curr)

        return (min(maxh, maxv) + 1) ** 2

Complexity analysis

Let h = hBars.length and v = vBars.length. Time: O(h log h + v log v). Auxiliary space: O(h + v) in the worst case for the language sort implementations.