Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A square needs two horizontal boundaries and two vertical boundaries with the same separation. Any fences between the chosen boundaries can be removed, so every pairwise distance in a direction is a possible side length. The answer is the largest distance achievable in both directions.

Approach

Include the field boundaries, at positions 1 and m horizontally and 1 and n vertically, in the corresponding fence lists. Enumerate every pair of horizontal positions and store their absolute difference in a set. Build the analogous set for vertical positions.

Intersect the two sets and find the largest common distance. Return its square modulo 1,000,000,007, or -1 when there is no common distance. Compare the actual side lengths before applying the modulus: modular area values do not preserve their original ordering. Absolute differences make sorting unnecessary.

class Solution:
    def maximizeSquareArea(self, m: int, n: int, hFences: List[int], vFences: List[int]) -> int:
        hFences += [1, m]
        vFences += [1, n]
        hf, vf = len(hFences), len(vFences)
        hd, vd = set(), set()

        for i in range(hf):
            for j in range(i + 1, hf):
                hd.add(abs(hFences[j] - hFences[i]))

        for i in range(vf):
            for j in range(i + 1, vf):
                vd.add(abs(vFences[j] - vFences[i]))

        # find intersection differences
        maxd = -1
        # for x in hd:
        # if x in vd:
        # maxd = max(maxd, x)
        # for x in vd:
        # if x in hd:
        # maxd = max(maxd, x)
        hd &= vd

        for x in hd:
            maxd = max(maxd, x)

        return (maxd ** 2) % (10**9 + 7) if maxd != -1 else -1

Complexity analysis

Let h = hFences.length + 2 and v = vFences.length + 2. Time: O(h^2 + v^2). Auxiliary space: O(h^2 + v^2) for the distance sets.