Skip to main content
Talentd

Maximum Square Area by Removing Fences From a Field - Solution & Explanation

MediumArrayHash TableEnumeration17 min readAsked at: Atlassian, Google, Bloomberg
Practice this problem

Problem Statement

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 109 + 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 <= 109
  • 1 <= hFences.length, vFences.length <= 600
  • 1 < hFences[i] < m
  • 1 < vFences[i] < n
  • hFences and vFences are unique.

Approach Overview

Problem Overview: You are given the height m and width n of a rectangular field along with positions of horizontal and vertical fences. You may remove any fences. The goal is to form the largest possible square using remaining fences as boundaries. The square side length must appear as both a horizontal distance and a vertical distance between two fences.

Approach 1: Brute Force Enumeration (O(h^2 * v^2) time, O(1) space)

Start by adding the outer borders of the field to the horizontal and vertical fence arrays. Then compute every pairwise distance between horizontal fences and every pairwise distance between vertical fences. For each horizontal distance, compare it with every vertical distance and check if they are equal. If a match exists, that distance forms a valid square side. Track the maximum side length and return its square as the area. This approach directly checks all combinations but becomes expensive because it compares every horizontal gap with every vertical gap.

Approach 2: Greedy Distance Matching with Hash Set (O(h^2 + v^2) time, O(v^2) space)

The key observation: a valid square exists when a horizontal gap equals a vertical gap. Instead of comparing all pairs, compute all vertical distances first and store them in a HashSet. Next, enumerate every pair of horizontal fences and compute their distance. For each distance, perform a constant-time lookup in the set of vertical distances. If the value exists, update the maximum side length. This removes the expensive nested comparison and reduces the search to simple enumeration plus hash lookup. The technique relies heavily on fast membership checks using a hash table.

Distances are generated by iterating over fence pairs, which is a common pattern when solving geometry-style problems with coordinate differences. Since fences define possible boundaries, every valid side length must come from the difference between two positions. The solution therefore combines array iteration with enumeration of all pairwise gaps.

After identifying the largest valid side length, compute the square area as side * side. If no matching side length exists between horizontal and vertical gaps, return -1. When the problem requires it, apply modulo 1e9 + 7 to avoid overflow.

Recommended for interviews: The hash-set enumeration approach is the expected solution. Interviewers often want to see that you first recognize the brute force idea, then optimize by storing one dimension's distances in a set for O(1) lookups. That shift from O(h^2 * v^2) comparisons to O(h^2 + v^2) demonstrates strong problem decomposition and familiarity with hash-based optimizations.

Approach 1: Greedy Approach

To solve the problem efficiently, we can utilize a greedy approach by focusing on the longest active segments left after considering the gaps created by fences. The problem naturally translates to finding the maximal gaps among ordered set of horizontal and vertical fences including the boundaries at 0 and m/n. This ensures that we consider the entire region formed between these pieces.

The solution uses an auxiliary function to sort the fence arrays and leverages the greedy strategy of finding the largest gaps created by the fences.

It calculates the maximum possible horizontal and vertical gaps (the longest segments) by adding the boundaries as implicit fences to determine possible square dimensions. These gaps are multiplied, and the solution is returned modulo 109 + 7.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(k log k), where k is the maximum length of hFences or vFences due to sorting.
Space Complexity: O(1), aside from input space.

Try this approach in the editor →

Approach 2: Enumeration

We can enumerate any two horizontal fences a and b in hFences, calculate the distance d between a and b, and record it in the hash table hs. Then, we enumerate any two vertical fences c and d in vFences, calculate the distance d between c and d, and record it in the hash table vs. Finally, we traverse the hash table hs. If a certain distance d in hs also exists in the hash table vs, it indicates that there exists a square field with a side length of d, and the area is d^2. We just need to take the largest d and calculate d^2 bmod 10^9 + 7.

The time complexity is O(h^2 + v^2), and the space complexity is O(h^2 + v^2). Here, h and v are the lengths of hFences and vFences, respectively.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach

Time Complexity: O(k log k), where k is the maximum length of hFences or vFences due to sorting.
Space Complexity: O(1), aside from input space.

Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Distance ComparisonO(h^2 * v^2)O(1)Conceptual baseline to understand the problem or when fence counts are extremely small
Hash Set Distance Matching (Greedy Enumeration)O(h^2 + v^2)O(v^2)Optimal approach for interviews and large inputs where fast distance lookup is required

Video Solution

Maximum Square Area by Removing Fences From a Field | Intuition | Leetcode 2975 | codestorywithMIK • codestorywithMIK • 6,941 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Square Area by Removing Fences From a Field easy or hard?
The problem is typically classified as Medium difficulty. The core challenge is recognizing that a square requires equal horizontal and vertical distances and that these distances come from fence pair differences. Once that insight is clear, a hash set optimization leads to an efficient solution.
Maximum Square Area by Removing Fences From a Field Python/Java solution
Most implementations compute all vertical gaps, store them in a set, and then iterate through horizontal gaps to find the largest matching value. The logic is straightforward to implement in Python using a set, in Java using HashSet, or in C++ using unordered_set. The algorithmic complexity remains O(h^2 + v^2).
How to solve Maximum Square Area by Removing Fences From a Field in O(n)?
A strict O(n) solution is not feasible because the side length candidates come from differences between fence pairs. The practical optimal approach computes all pairwise distances in each direction, which results in O(h^2 + v^2). Using a hash set keeps lookups constant time and avoids O(h^2 * v^2) comparisons.
What is the best approach for Maximum Square Area by Removing Fences From a Field?
The most efficient approach enumerates all vertical fence distances and stores them in a hash set, then checks horizontal fence distances against that set. This reduces comparisons dramatically and runs in O(h^2 + v^2) time. The hash lookup ensures constant‑time checks when verifying whether a square side length exists in both directions.
Is Maximum Square Area by Removing Fences From a Field asked at Google/Amazon/Meta?
Variants of grid geometry and coordinate distance problems appear frequently in interviews at companies like Google, Amazon, and Meta. Problems involving pairwise differences, hash sets, and geometric constraints are common because they test both algorithmic thinking and data structure usage.
What data structure is used in Maximum Square Area by Removing Fences From a Field?
The key data structure is a hash set that stores all vertical fence distance values. This allows constant‑time membership checks when evaluating horizontal distances. Arrays store fence positions, and enumeration generates candidate side lengths.
What is the time complexity of Maximum Square Area by Removing Fences From a Field?
The optimized solution runs in O(h^2 + v^2) time, where h is the number of horizontal fences and v is the number of vertical fences. All pairwise gaps are computed for each direction, and hash set lookups check for matching lengths. Space complexity is O(v^2) for storing vertical distances.

Ready to solve this problem?

Practice Maximum Square Area by Removing Fences From a Field with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximize Area of Square Hole in Grid