🚜 Beginner-Friendly Guide 'Maximum Square Area by Removing Fences From a Field' – LeetCode 2975 (C++, Python, JavaScript)

Navigating the world of computational geometry can be tricky. This problem asks us to look past the physical "fences" and instead focus on the gaps between them to find the perfect geometric symmetry.

---

Problem Summary

You're given:

• Two integers, and , representing the outer boundaries of a rectangular field.
• Two arrays, hFences and vFences, which represent the positions of existing horizontal and vertical fences inside that field.
• Implicit outer fences at positions 1 and (horizontal) and 1 and (vertical).

Your goal:

Find the maximum area of a square field that can be formed by choosing any two horizontal fences and any two vertical fences. If no square can be formed, return -1. Otherwise, return the area modulo .

Example :
Input: m = 4, n = 3, hFences = [2,3], vFences = [2]

Output: 4
Explanation: Removing the horizontal fence at 2 and the vertical fence at 2 will give a square field of area 4.

---

Intuition

To form a square, the distance between your two chosen horizontal fences (the height) must be exactly equal to the distance between your two chosen vertical fences (the width).

The strategy is broken down into three logical steps:

1. Include the Boundaries: The problem states we can use the outer edges of the field. We must add 1 and to our horizontal list, and 1 and to our vertical list.
2. Find All Possible Gaps: For the horizontal fences, we calculate every possible distance between any two fences. If we have fences at positions and , the gap is . We store all these possible "heights" in a hash set for quick lookup.
3. Find the Maximum Match: We then calculate every possible distance between any two vertical fences (the "widths"). For each width we find, we check if that same value exists in our set of horizontal heights. If it does, we have a square! We keep track of the largest such value found.

---

Code Blocks

C++

class Solution {
public:
    static constexpr int mod = 1e9 + 7;
    unordered_set<int> seen;
    int maxL = 0;

    void findLen(vector<int>& fences, int sz, bool isVertical) {
        sort(fences.begin(), fences.end());
        for (int l = 0; l < sz - 1; l++) {
            for (int r = l + 1; r < sz; r++) {
                int len = fences[r] - fences[l];
                if (isVertical) {
                    if (len > maxL && seen.count(len)) {
                        maxL = len;
                    }
                } else {
                    seen.insert(len);
                }
            }
        }
    }

    int maximizeSquareArea(int m, int n, vector<int>& hFences, vector<int>& vFences) {
        hFences.push_back(1);
        hFences.push_back(m);
        vFences.push_back(1);
        vFences.push_back(n);

        // Process horizontal fences first to populate the set
        findLen(hFences, hFences.size(), false);
        // Process vertical fences to find the max common length
        findLen(vFences, vFences.size(), true);

        if (maxL == 0) return -1;
        return (long long)maxL * maxL % mod;
    }
};

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])
        hFences.sort()
        vFences.sort()

        # Calculate all possible horizontal gaps
        h_gaps = set()
        for i in range(len(hFences)):
            for j in range(i + 1, len(hFences)):
                h_gaps.add(hFences[j] - hFences[i])

        max_l = -1
        # Check all possible vertical gaps against horizontal gaps
        for i in range(len(vFences)):
            for j in range(i + 1, len(vFences)):
                gap = vFences[j] - vFences[i]
                if gap in h_gaps:
                    max_l = max(max_l, gap)

        if max_l == -1:
            return -1

        return (max_l * max_l) % (10**9 + 7)

JavaScript

/**
 * @param {number} m
 * @param {number} n
 * @param {number[]} hFences
 * @param {number[]} vFences
 * @return {number}
 */
var maximizeSquareArea = function(m, n, hFences, vFences) {
    const mod = BigInt(1e9 + 7);
    hFences.push(1, m);
    vFences.push(1, n);

    hFences.sort((a, b) => a - b);
    vFences.sort((a, b) => a - b);

    const hGaps = new Set();
    for (let i = 0; i < hFences.length; i++) {
        for (let j = i + 1; j < hFences.length; j++) {
            hGaps.add(hFences[j] - hFences[i]);
        }
    }

    let maxL = -1;
    for (let i = 0; i < vFences.length; i++) {
        for (let j = i + 1; j < vFences.length; j++) {
            let gap = vFences[j] - vFences[i];
            if (hGaps.has(gap)) {
                max_l = Math.max(maxL, gap);
                if (gap > maxL) maxL = gap;
            }
        }
    }

    if (maxL === -1) return -1;
    return Number((BigInt(maxL) * BigInt(maxL)) % mod);
};

---

Key Takeaways

• Hash Sets for Intersection: When you need to find common elements between two sets of calculated values, a Hash Set (or unordered_set in C++) provides average time complexity for lookups.
• Brute Force on Constraints: Sometimes "brute force" is the intended solution. Since the number of fences is relatively small (up to 600), an approach to find all gaps is efficient enough.
• Handling Large Numbers: Always be mindful of integer overflow. When calculating area, use long long (C++) or BigInt (JavaScript) before applying the modulo .

---

Final Thoughts

This problem is a fantastic example of how to simplify a 2D geometric problem into two independent 1D problems. In the real world, this logic is used in computer vision and graphic rendering, where systems must identify rectangular or square bounds within a coordinate system, such as detecting UI elements on a screen or processing architectural blueprints. As a mentor, I encourage you to always look for ways to break multi-dimensional constraints into simpler, individual components.