2975. Maximum Square Area by Removing Fences From a Field

/**
 * Problem: LeetCode 2975 - Maximum Square Area by Removing Fences From a Field
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int maximizeSquareArea(int m, int n, int[] hFences, int[] vFences) {
        final long MOD = 1_000_000_007L;

        // Include fixed boundary fences 1 and m for horizontal, 1 and n for vertical
        int[] h = new int[hFences.length + 2];
        h[0] = 1;
        h[1] = m;
        System.arraycopy(hFences, 0, h, 2, hFences.length);
        Arrays.sort(h);

        int[] v = new int[vFences.length + 2];
        v[0] = 1;
        v[1] = n;
        System.arraycopy(vFences, 0, v, 2, vFences.length);
        Arrays.sort(v);

        // Store all possible gap sizes between any pair of horizontal fences
        Set<Integer> hDiffs = new HashSet<>();
        for (int i = 0; i < h.length; i++) {
            for (int j = i + 1; j < h.length; j++) {
                hDiffs.add(h[j] - h[i]);
            }
        }

        // Find the maximum gap size that exists in both horizontal and vertical differences
        long maxSide = -1;
        for (int i = 0; i < v.length; i++) {
            for (int j = i + 1; j < v.length; j++) {
                int diff = v[j] - v[i];
                if (hDiffs.contains(diff)) {
                    maxSide = Math.max(maxSide, diff);
                }
            }
        }

        if (maxSide == -1) {
            return -1;
        }

        return (int) ((maxSide * maxSide) % MOD);
    }
}

"""
Problem: LeetCode 2975 - Maximum Square Area by Removing Fences From a Field
Difficulty: Medium
Language: Python
Author: CodeByTushu
"""
from typing import List


class Solution:

    def maximizeSquareArea(
        self, m: int, n: int, hFences: List[int], vFences: List[int]
    ) -> int:
        MOD = 1_000_000_007

        # Add boundary fences 1 and m, and 1 and n
        h = sorted(hFences + [1, m])
        v = sorted(vFences + [1, n])

        # Compute all possible horizontal gap sizes
        h_diffs = set()
        for i in range(len(h)):
            for j in range(i + 1, len(h)):
                h_diffs.add(h[j] - h[i])

        # Find the maximum gap size common to both horizontal and vertical
        max_side = -1
        for i in range(len(v)):
            for j in range(i + 1, len(v)):
                diff = v[j] - v[i]
                if diff in h_diffs:
                    if diff > max_side:
                        max_side = diff

        if max_side == -1:
            return -1

        return (max_side * max_side) % MOD

/**
 * Problem: LeetCode 2975 - Maximum Square Area by Removing Fences From a Field
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <algorithm>
#include <unordered_set>

using namespace std;

class Solution {
public:
    int maximizeSquareArea(int m, int n, vector<int>& hFences, vector<int>& vFences) {
        const long long MOD = 1000000007LL;

        // Add boundary fences
        vector<int> h = hFences;
        h.push_back(1);
        h.push_back(m);
        sort(h.begin(), h.end());

        vector<int> v = vFences;
        v.push_back(1);
        v.push_back(n);
        sort(v.begin(), v.end());

        // Collect all horizontal differences in a hash set
        unordered_set<int> hDiffs;
        hDiffs.reserve(h.size() * (h.size() - 1) / 2);
        for (size_t i = 0; i < h.size(); i++) {
            for (size_t j = i + 1; j < h.size(); j++) {
                hDiffs.insert(h[j] - h[i]);
            }
        }

        // Find the maximum side length common to both
        long long maxSide = -1;
        for (size_t i = 0; i < v.size(); i++) {
            for (size_t j = i + 1; j < v.size(); j++) {
                int diff = v[j] - v[i];
                if (hDiffs.count(diff)) {
                    maxSide = max(maxSide, static_cast<long long>(diff));
                }
            }
        }

        if (maxSide == -1) {
            return -1;
        }

        return static_cast<int>((maxSide * maxSide) % MOD);
    }
};

/**
 * Problem: LeetCode 2975 - Maximum Square Area by Removing Fences From a Field
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * @param {number} m
 * @param {number} n
 * @param {number[]} hFences
 * @param {number[]} vFences
 * @return {number}
 */
var maximizeSquareArea = function(m, n, hFences, vFences) {
    const MOD = 1000000007n;

    // Add boundary fences and sort
    const h = [...hFences, 1, m].sort((a, b) => a - b);
    const v = [...vFences, 1, n].sort((a, b) => a - b);

    // Compute all possible horizontal differences
    const hDiffs = new Set();
    for (let i = 0; i < h.length; i++) {
        for (let j = i + 1; j < h.length; j++) {
            hDiffs.add(h[j] - h[i]);
        }
    }

    // Find the maximum side length common to both dimensions
    let maxSide = -1n;
    for (let i = 0; i < v.length; i++) {
        for (let j = i + 1; j < v.length; j++) {
            const diff = v[j] - v[i];
            if (hDiffs.has(diff)) {
                const diffBig = BigInt(diff);
                if (diffBig > maxSide) {
                    maxSide = diffBig;
                }
            }
        }
    }

    if (maxSide === -1n) {
        return -1;
    }

    return Number((maxSide * maxSide) % MOD);
};