Problem Statement in English

You’re given two integers m and n representing the dimensions of a field, along with two integer arrays hFences and vFences representing the positions of horizontal and vertical fences in the field, respectively.

You can remove any number of horizontal and vertical fences from the field. After removing the fences, you want to find the maximum possible area of a square that can be formed within the remaining fences.

You cannot remove the 4 bounding fences of the field.

Approach

The idea is that we need to find some vertical gap which also exists as a horizontal gap, so that we can form a square of that side length.

We can do this by calculating all possible distances between the horizontal fences and storing them in a set.

Then, we calculate all possible distances between the vertical fences and check if any of these distances exist in the set of horizontal distances.

The maximum such distance will give us the side length of the largest square that can be formed. Finally, we return the area of this square modulo 109+710^9 + 7.

If no such square can be formed, we return -1.

Solution in Python


class Solution:
    def maximizeSquareArea(
        self, m: int, n: int, hFences: List[int], vFences: List[int]
    ) -> int:
        hFences.extend([1, m])
        vFences.extend([1, n])

        stt = set()
        ans = 0

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

        for i in range(len(vFences)):
            for j in range(i + 1, len(vFences)):
                val = abs(vFences[j] - vFences[i])
                if val in stt:
                    ans = max(ans, val)

        if ans == 0:
            return -1
        return (ans * ans) % (10**9 + 7)

Complexity

  • Time: O((H+V)2)O((H + V)^2)
    Since we are using two nested loops to calculate all possible distances between the fences, where H is the number of horizontal fences and V is the number of vertical fences.

  • Space: O(H+V)O(H + V)
    We are using a set to store the unique distances between the horizontal fences.

Mistakes I Made

I had to look this up :(

And we are done.