Daily LeetCode - by Vítor Belim

Description

There is a large (m - 1) x (n - 1) rectangular field with corners at (1, 1) and (m, n) containing some horizontal and vertical fences given in arrays hFences and vFences respectively.

Horizontal fences are from the coordinates (hFences[i], 1) to (hFences[i], n) and vertical fences are from the coordinates (1, vFences[i]) to (m, vFences[i]).

Return the maximum area of a square field that can be formed by removing some fences (possibly none) or -1 if it is impossible to make a square field.

Since the answer may be large, return it modulo 10⁹+ 7.

Note: The field is surrounded by two horizontal fences from the coordinates (1, 1) to (1, n) and (m, 1) to (m, n) and two vertical fences from the coordinates (1, 1) to (m, 1) and (1, n) to (m, n). These fences cannot be removed.

Example 1:

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.

Example 2:

Input: m = 6, n = 7, hFences = [2], vFences = [4]
Output: -1
Explanation: It can be proved that there is no way to create a square field by removing fences.

Constraints:

3 <= m, n <= 10⁹
1 <= hFences.length, vFences.length <= 600
1 < hFences[i] < m
1 < vFences[i] < n
hFences and vFences are unique.

Solutions

This function finds the largest square that can fit in an m × n grid with obstacles (fences) at specific positions. It works by: (1) adding the grid boundaries (1 and m/n) to the fence arrays and sorting them, (2) computing all possible horizontal distances between fence pairs and storing them in a Set, (3) checking all possible vertical distances and finding the largest one that matches a horizontal distance (since a square needs equal width and height), and (4) returning the area of that square (side²) modulo 10^9 + 7, or -1 if no valid square exists. The key insight is that a valid square's side length must be achievable in both dimensions — it must appear as a gap between two horizontal fences and as a gap between two vertical fences.

Language: javascript(2026-01-16 09:52)DONE

CPU Performance100.00%

Memory Performance0.00%

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

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

    const hSpace = new Set();

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

    let maxSpace = 0;

    for (let i = 0; i < vFences.length; i++) {
        for (let j = i + 1; j < vFences.length; j++) {
            const vSpace = vFences[j] - vFences[i];

            if (vSpace > maxSpace && hSpace.has(vSpace)) {
                maxSpace = vSpace;
            }
        }
    }

    if (maxSpace === 0) {
        return -1;
    }

    const maxSpaceBigInt = BigInt(maxSpace);
    const MOD = BigInt(10 ** 9 + 7);

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

Description

Solutions

AI Explanation