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 <= 1091 <= hFences.length, vFences.length <= 6001 < hFences[i] < m1 < vFences[i] < nhFences and vFences are unique.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.
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.
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.
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.
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(k log k), where k is the maximum length of hFences or vFences due to sorting. |
| Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Distance Comparison | O(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 |
Maximum Square Area by Removing Fences From a Field | Intuition | Leetcode 2975 | codestorywithMIK • codestorywithMIK • 6,724 views views
Watch 9 more video solutions →Practice Maximum Square Area by Removing Fences From a Field with our built-in code editor and test cases.
Practice on FleetCode