# Maximum Square Area by Removing Fences From a Field
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-square-area-by-removing-fences-from-a-field)
Canonical: https://scaleengineer.com/dsa/problems/maximum-square-area-by-removing-fences-from-a-field
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array, Hash Table
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian)
---
## Problem
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:**

![](https://assets.glich.co/dsa/maximum-square-area-by-removing-fences-from-a-field/image0.png)

**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:**

![](https://assets.glich.co/dsa/maximum-square-area-by-removing-fences-from-a-field/image1.png)

**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.

# Approaches
## Brute-Force Comparison of All Possible Distances
This straightforward approach calculates every possible distance between pairs of horizontal fences and every possible distance between pairs of vertical fences. It then compares these two sets of distances to find the largest common value, which corresponds to the side of the maximum possible square.
**Time:** O(L_h^2 * L_v^2), where `L_h` and `L_v` are the number of horizontal and vertical fences, respectively. Generating the distance lists takes O(L_h^2) and O(L_v^2). The nested loop to find the maximum common side length dominates the complexity. · **Space:** O(L_h^2 + L_v^2) to store the lists of all possible horizontal and vertical distances, where `L_h` and `L_v` are the lengths of the input fence arrays.
**Pros:** Conceptually simple and easy to understand and implement.
**Cons:** Extremely inefficient due to the nested comparison loop, which has a time complexity proportional to the fourth power of the input size.; Will likely result in a 'Time Limit Exceeded' error for constraints specified in the problem.
### Explanation
To form a square, we need to select two horizontal fences and two vertical fences such that the distance between the horizontal pair equals the distance between the vertical pair. The core idea is to generate all potential side lengths and find the maximum one that can be formed both horizontally and vertically.

First, we must account for the non-removable boundary fences. The complete set of horizontal fence locations includes `1`, `m`, and all values from `hFences`. Similarly, the vertical fence locations include `1`, `n`, and all values from `vFences`.

We generate a list of all possible heights by taking the absolute difference of every pair of horizontal fence locations. Then, we generate a similar list of all possible widths from the vertical fence locations.

With these two lists, `h_distances` and `v_distances`, we perform a nested loop. We iterate through each height in `h_distances` and compare it against every width in `v_distances`. We keep track of the largest distance that appears in both lists. If no common distance is found, it's impossible to form a square. Otherwise, we use the largest common side length to calculate the maximum square area, taking the result modulo `10^9 + 7`.

Here is the implementation in Java:
```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int maximizeSquareArea(int m, int n, int[] hFences, int[] vFences) {
        List<Long> allHFences = new ArrayList<>();
        allHFences.add(1L);
        allHFences.add((long)m);
        for (int h : hFences) {
            allHFences.add((long)h);
        }

        List<Long> allVFences = new ArrayList<>();
        allVFences.add(1L);
        allVFences.add((long)n);
        for (int v : vFences) {
            allVFences.add((long)v);
        }

        List<Long> hDistances = new ArrayList<>();
        for (int i = 0; i < allHFences.size(); i++) {
            for (int j = i + 1; j < allHFences.size(); j++) {
                hDistances.add(Math.abs(allHFences.get(i) - allHFences.get(j)));
            }
        }

        List<Long> vDistances = new ArrayList<>();
        for (int i = 0; i < allVFences.size(); i++) {
            for (int j = i + 1; j < allVFences.size(); j++) {
                vDistances.add(Math.abs(allVFences.get(i) - allVFences.get(j)));
            }
        }

        long maxSide = -1;
        for (long hDist : hDistances) {
            for (long vDist : vDistances) {
                if (hDist == vDist) {
                    maxSide = Math.max(maxSide, hDist);
                }
            }
        }

        if (maxSide == -1) {
            return -1;
        }

        long mod = 1_000_000_007;
        long area = (maxSide * maxSide) % mod;
        return (int) area;
    }
}
```
Note: Since `m` and `n` can be up to `10^9`, the fence coordinates and their differences can be large. Using `long` for these values prevents potential overflow issues.
### Algorithm
- 1. Create a list `all_hFences` by adding boundary fences `1` and `m` to the `hFences` array. Use `long` type to handle large coordinates.
- 2. Create a list `all_vFences` by adding boundary fences `1` and `n` to the `vFences` array, also using `long` type.
- 3. Initialize an empty list `h_distances` to store possible horizontal side lengths.
- 4. Iterate through all pairs of fences in `all_hFences` and add their absolute difference to `h_distances`.
- 5. Initialize an empty list `v_distances` to store possible vertical side lengths.
- 6. Iterate through all pairs of fences in `all_vFences` and add their absolute difference to `v_distances`.
- 7. Initialize a variable `max_side = -1` to track the maximum common side length.
- 8. Use a nested loop to iterate through every distance in `h_distances` and `v_distances`.
- 9. If a common distance `d` is found (i.e., `h_dist == v_dist`), update `max_side = max(max_side, d)`.
- 10. After the loops, if `max_side` is still -1, it means no square can be formed, so return -1.
- 11. Otherwise, calculate the area as `(max_side * max_side) % 1000000007` and return the result.

## Efficient Search Using a Hash Set
This approach significantly improves upon the brute-force method by optimizing the search for a common side length. Instead of a slow nested loop comparison, it uses a hash set to achieve near-constant time lookups. We first compute all possible horizontal distances and store them in a hash set. Then, for each possible vertical distance, we efficiently check if it exists in the set.
**Time:** O(L_h^2 + L_v^2), where `L_h` and `L_v` are the lengths of the fence arrays. Populating the hash set takes O(L_h^2) time. Iterating through vertical fence pairs and performing hash set lookups takes O(L_v^2) time on average. · **Space:** O(L_h^2) to store the set of unique horizontal distances. In the worst case, all O(L_h^2) distances could be unique.
**Pros:** Highly efficient compared to the brute-force method, with a much better time complexity.; Provides an optimal solution that passes within the time limits for the given problem constraints.
**Cons:** Requires additional space to store the hash set, which can be up to O(L_h^2) in size.
### Explanation
The fundamental logic remains the same: find the largest side length `s` that can be formed by both a pair of horizontal fences and a pair of vertical fences. The optimization comes from how we find this common `s`.

We begin by creating the complete sets of horizontal and vertical fence coordinates, including the boundaries. Then, we iterate through all pairs of horizontal fences, calculate their distance, and store each unique distance in a `HashSet`. This data structure provides average O(1) time complexity for insertion and search operations.

After populating the hash set with all possible horizontal distances, we iterate through all pairs of vertical fences. For each calculated vertical distance, we check if it's present in our hash set. If it is, we've found a valid side length for a square. We keep track of the maximum such side length found.

This eliminates the need for the costly O(L_h^2 * L_v^2) comparison, reducing the search part of the algorithm to just O(L_v^2). The overall performance becomes dominated by the generation of distances, which is much more manageable.

Here is the Java implementation:
```java
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public int maximizeSquareArea(int m, int n, int[] hFences, int[] vFences) {
        List<Long> allHFences = new ArrayList<>();
        allHFences.add(1L);
        allHFences.add((long)m);
        for (int h : hFences) {
            allHFences.add((long)h);
        }

        List<Long> allVFences = new ArrayList<>();
        allVFences.add(1L);
        allVFences.add((long)n);
        for (int v : vFences) {
            allVFences.add((long)v);
        }

        Set<Long> hDistancesSet = new HashSet<>();
        for (int i = 0; i < allHFences.size(); i++) {
            for (int j = i + 1; j < allHFences.size(); j++) {
                hDistancesSet.add(Math.abs(allHFences.get(i) - allHFences.get(j)));
            }
        }

        long maxSide = -1;
        for (int i = 0; i < allVFences.size(); i++) {
            for (int j = i + 1; j < allVFences.size(); j++) {
                long vDist = Math.abs(allVFences.get(i) - allVFences.get(j));
                if (hDistancesSet.contains(vDist)) {
                    maxSide = Math.max(maxSide, vDist);
                }
            }
        }

        if (maxSide == -1) {
            return -1;
        }

        long mod = 1_000_000_007;
        long area = (maxSide * maxSide) % mod;
        return (int) area;
    }
}
```
### Algorithm
- 1. Augment `hFences` with boundary fences `1` and `m` into a list `all_hFences` of type `long`.
- 2. Augment `vFences` with boundary fences `1` and `n` into a list `all_vFences` of type `long`.
- 3. Initialize a `HashSet<Long>` called `h_distances_set`.
- 4. Iterate through all pairs of fences in `all_hFences`, calculate their absolute difference, and add it to `h_distances_set`.
- 5. Initialize `max_side = -1`.
- 6. Iterate through all pairs of fences in `all_vFences`.
- 7. For each pair, calculate the distance `v_dist`.
- 8. Check if `h_distances_set` contains `v_dist`. This is an efficient O(1) average time operation.
- 9. If it does, update `max_side = max(max_side, v_dist)`.
- 10. If `max_side` is -1 after checking all vertical distances, return -1.
- 11. Otherwise, compute `(max_side * max_side) % 1000000007` and return the result.

# Solutions
### Java

```java
class Solution {
public
  int maximizeSquareArea(int m, int n, int[] hFences, int[] vFences) {
    Set<Integer> hs = f(hFences, m);
    Set<Integer> vs = f(vFences, n);
    hs.retainAll(vs);
    int ans = -1;
    final int mod = (int)1 e9 + 7;
    for (int x : hs) {
      ans = Math.max(ans, x);
    }
    return ans > 0 ? (int)(1L * ans * ans % mod) : -1;
  }
private
  Set<Integer> f(int[] nums, int k) {
    int n = nums.length;
    nums = Arrays.copyOf(nums, n + 2);
    nums[n] = 1;
    nums[n + 1] = k;
    Arrays.sort(nums);
    Set<Integer> s = new HashSet<>();
    for (int i = 0; i < nums.length; ++i) {
      for (int j = 0; j < i; ++j) {
        s.add(nums[i] - nums[j]);
      }
    }
    return s;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximizeSquareArea(int m, int n, vector<int> &hFences,
                         vector<int> &vFences) {
    auto f = [](vector<int> &nums, int k) {
      nums.push_back(k);
      nums.push_back(1);
      sort(nums.begin(), nums.end());
      unordered_set<int> s;
      for (int i = 0; i < nums.size(); ++i) {
        for (int j = 0; j < i; ++j) {
          s.insert(nums[i] - nums[j]);
        }
      }
      return s;
    };
    auto hs = f(hFences, m);
    auto vs = f(vFences, n);
    int ans = 0;
    for (int h : hs) {
      if (vs.count(h)) {
        ans = max(ans, h);
      }
    }
    const int mod = 1e9 + 7;
    return ans > 0 ? 1LL * ans * ans % mod : -1;
  }
};

```

### Python

```python
class Solution:
    def maximizeSquareArea(self, m: int, n: int, hFences: List[int], vFences: List[int]) -> int: def f(nums: List[int], k: int) -> Set[int]: nums . extend([1, k]) nums . sort() return {b - a for a, b in combinations(nums, 2)} mod = 10 ** 9 + 7 hs = f(hFences, m) vs = f(vFences, n) ans = max(hs & vs, default=0) return ans ** 2 % mod if ans else - 1

```