2975. Maximum Square Area by Removing Fences From a Field

Array
Hash Table
Sorting

TIME

O(h² + v²)

SPACE

O(h²)

Intuition

We need to find the maximum square that can be formed by selecting two horizontal fences and two vertical fences such that the distance between them is equal. The boundary fences (at positions 1 and m for horizontal, 1 and n for vertical) are always present and cannot be removed.

Solution

Include boundary fences: Add positions 1 and m to horizontal fences, add 1 and n to vertical fences.
Compute all possible distances: For horizontal fences, compute all pairwise distances and store them in a set.
Find common distances: For each pairwise distance in vertical fences, check if the same distance exists in the horizontal set.
Track maximum: Keep track of the maximum distance that exists in both sets, this gives the maximum side length.
Return result: If a common distance exists, return side² mod 10^9 + 7. Otherwise, return -1.

Why This Works

Removing fences between two positions creates a gap equal to their distance
A square requires equal horizontal and vertical gaps
We enumerate all possible gaps and find the largest common one

Complexity

Time: O(h² + v²) where h = len(hFences), v = len(vFences), generating all pairwise distances
Space: O(h²), storing horizontal distances in a set

Edge Cases

No common distance exists → return -1
Only boundary fences can form a square
Large values require modulo operation on area (not side)

Code

from typing import List


class Solution:
    def maximizeSquareArea(
        self, m: int, n: int, hFences: List[int], vFences: List[int]
    ) -> int:
        """
        2975. Maximum Square Area by Removing Fences From a Field
        Time: O(h² + v²)
        Space: O(h²)
        """
        MOD = 10**9 + 7

        horizontal_fences = [1] + hFences + [m]
        vertical_fences = [1] + vFences + [n]

        horizontal_fences.sort()
        vertical_fences.sort()

        distance_set = set()

        for i in range(len(horizontal_fences)):
            for j in range(i + 1, len(horizontal_fences)):
                distance_set.add(horizontal_fences[j] - horizontal_fences[i])

        max_side = -1

        for i in range(len(vertical_fences)):
            for j in range(i + 1, len(vertical_fences)):
                distance = vertical_fences[j] - vertical_fences[i]
                if distance in distance_set:
                    max_side = max(max_side, distance)

        if max_side == -1:
            return -1

        return (max_side * max_side) % MOD

import java.util.Arrays;
import java.util.HashSet;

/**
 * 2975. Maximum Square Area by Removing Fences From a Field
 * Time: O(h² + v²)
 * Space: O(h²)
 */
class Solution {
    public int maximizeSquareArea(int m, int n, int[] hFences, int[] vFences) {
        final long MOD = 1_000_000_007L;
        
        int[] h = new int[hFences.length + 2];
        int[] v = new int[vFences.length + 2];
        
        h[0] = 1;
        h[h.length - 1] = m;
        for (int i = 0; i < hFences.length; i++) {
            h[i + 1] = hFences[i];
        }
        
        v[0] = 1;
        v[v.length - 1] = n;
        for (int i = 0; i < vFences.length; i++) {
            v[i + 1] = vFences[i];
        }
        
        Arrays.sort(h);
        Arrays.sort(v);
        
        HashSet<Integer> hDist = new HashSet<>();
        for (int i = 0; i < h.length; i++) {
            for (int j = i + 1; j < h.length; j++) {
                hDist.add(h[j] - h[i]);
            }
        }
        
        int maxSide = -1;
        for (int i = 0; i < v.length; i++) {
            for (int j = i + 1; j < v.length; j++) {
                int d = v[j] - v[i];
                if (hDist.contains(d)) {
                    maxSide = Math.max(maxSide, d);
                }
            }
        }
        
        if (maxSide == -1) {
            return -1;
        }
        
        long area = (1L * maxSide * maxSide) % MOD;
        return (int) area;
    }
}