Watch 10 video solutions for Maximum Square Area by Removing Fences From a Field, a medium level problem involving Array, Hash Table, Enumeration. This walkthrough by codestorywithMIK has 6,724 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |