Maximum Square Area by Removing Fences From a Field
Source: leetcode
Difficulty: Medium
Tags: array, hash-table, enumeration

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.leetcode.com/uploads/2023/11/05/screenshot-from-2023-11-05-22-40-25.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.leetcode.com/uploads/2023/11/22/maxsquareareaexample1.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.




C++ solution:
class Solution {
public:
    int maximizeSquareArea(int m, int n, vector<int>& hFences, vector<int>& vFences) {
        constexpr long MOD = 1'000'000'007;
        auto calcSides =
            [](const std::vector<int> &fences, int max_side) -> std::priority_queue<int>
        {
            const int fs = static_cast<int>(fences.size());
            std::priority_queue<int> sides;
            for (int i = 0; i < fs - 1; ++i)
                for (int j = i + 1; j < fs; ++j)
                    if (int side = std::abs(fences[j] - fences[i]); side <= max_side)
                        sides.emplace(side);
            return sides;
        };
        if (m == n)
            return static_cast<int>(static_cast<long>(m - 1) * (n - 1) % MOD);
        hFences.push_back(1);
        hFences.push_back(m);
        vFences.push_back(1);
        vFences.push_back(n);
        std::priority_queue<int> h_sides = calcSides(hFences, std::min(m, n) - 1),
                                v_sides = calcSides(vFences, std::min(m, n) - 1);
        while (!h_sides.empty() && !v_sides.empty())
        {
            long h_top = h_sides.top(), v_top = v_sides.top();
            if (h_top == v_top)
                return static_cast<int>(h_top * v_top % MOD);
            if (h_top > v_top) h_sides.pop();
            else v_sides.pop();
        }
        return -1;
    }
};

Go solution:
func maximizeSquareArea(m int, n int, hFences []int, vFences []int) int {
	hFences = append([]int{1}, append(hFences, m)...)
	vFences = append([]int{1}, append(vFences, n)...)
	sort.Ints(hFences)
	sort.Ints(vFences)

	hDiffs := make(map[int]bool)
	for i := 0; i < len(hFences)-1; i++ {
		for j := i + 1; j < len(hFences); j++ {
			hDiffs[hFences[j]-hFences[i]] = true
		}
	}

	maxArea := int64(-1)
	for x := 0; x < len(vFences)-1; x++ {
		for y := x + 1; y < len(vFences); y++ {
			vDiff := vFences[y] - vFences[x]
			if hDiffs[vDiff] {
				maxArea = max(maxArea, int64(vDiff*vDiff))
			}
		}
	}

	return int(maxArea % 1_000_000_007)
}

func max(a int64, b int64) int64 {
	if a > b {
		return a
	}
	return b
}

// BRUTE FORCE
// func maximizeSquareArea(m int, n int, hFences []int, vFences []int) int {
// 	hFences = append([]int{1}, append(hFences, m)...)
// 	vFences = append([]int{1}, append(vFences, n)...)
// 	sort.Ints(hFences)
// 	sort.Ints(vFences)

// 	hDiff, vDiff := []int{}, []int{}
// 	for i := 0; i < len(hFences)-1; i++ {
// 		for j := i + 1; j < len(hFences); j++ {
// 			hDiff = append(hDiff, hFences[j]-hFences[i])
// 		}
// 	}
// 	sort.Ints(hDiff)

// 	for x := 0; x < len(vFences)-1; x++ {
// 		for y := x + 1; y < len(vFences); y++ {
// 			vDiff = append(vDiff, vFences[y]-vFences[x])
// 		}
// 	}
// 	sort.Ints(vDiff)

// 	maxCommVal := -1
// 	i, j := 0, 0
// 	for i < len(hDiff) && j < len(vDiff) {
// 		if hDiff[i] == vDiff[j] {
// 			maxCommVal = hDiff[i]
// 			i++
// 			j++
// 		} else if hDiff[i] < vDiff[j] {
// 			i++
// 		} else {
// 			j++
// 		}
// 	}

// 	if maxCommVal == -1 {
// 		return -1
// 	}

// 	MODULO := 1_000_000_007
// 	return ((maxCommVal % MODULO) * (maxCommVal % MODULO)) % MODULO
// }

Java solution:
class Solution {
    public int maximizeSquareArea(int m, int n, int[] hFences, int[] vFences) {
        Arrays.sort(hFences);
        Arrays.sort(vFences);

        List<Integer> horizontal = new ArrayList<>();
        for (int fence : hFences) {
            horizontal.add(fence);
        }
        horizontal.add(0, 1);
        horizontal.add(m);

        List<Integer> vertical = new ArrayList<>();
        for (int fence : vFences) {
            vertical.add(fence);
        }
        vertical.add(0, 1);
        vertical.add(n);

        int ans = -1;
        Map<Integer, Integer> cnt = new HashMap<>();

        for (int i = 0; i < horizontal.size(); i++) {
            for (int j = i + 1; j < horizontal.size(); j++) {
                cnt.put(horizontal.get(j) - horizontal.get(i), 1);
            }
        }

        for (int i = 0; i < vertical.size(); i++) {
            for (int j = i + 1; j < vertical.size(); j++) {
                if (cnt.containsKey(vertical.get(j) - vertical.get(i))) {
                    ans = Math.max(ans, vertical.get(j) - vertical.get(i));
                }
            }
        }

        if (ans == -1) return ans;

        int mod = 1000000007;
        return (int) ((1L * ans * ans) % mod);
    }
}

JavaScript solution:
const maximizeSquareArea = (m, n, hFences, vFences) => {
  let maxSide = 0

  const fencedX = [1 , ...vFences, n]
  const fencedY = [1 , ...hFences, m]

  const maxSizeX = n - 1
  const maxSizeY = m - 1

  // not sorted, apparently, just .sort() doesn't work for long ones
  fencedX.sort((a, b) => a - b) 
  fencedY.sort((a, b) => a - b)

  let sideSize

  // check all sizes along x axis, start with size of all sections combined e.g. fencedX[3-1] - fencedX[0] for 2 sections
  const sectionsX = new Set() 
  for (let numOfSections = fencedX.length - 1; numOfSections >= 1; numOfSections--) {
    // don't need to try fence indecies less than number of sections you combine
    for (let fenceIndex = fencedX.length - 1; fenceIndex >= numOfSections; fenceIndex--) {
      sideSize = fencedX[fenceIndex] - fencedX[fenceIndex - numOfSections]

      // sizes in X larger than largest size in Y are useless
      if (sideSize > maxSizeY) continue

      sectionsX.add(sideSize)
    }    
  }

  // check all sizes along y axis, start with size of all sections combined e.g. fencedX[]
  for (let numOfSections = fencedY.length - 1; numOfSections >= 1; numOfSections--) {
  
    // don't need to try fence indecies less than number of sections you combine
    for (let fenceIndex = fencedY.length - 1; fenceIndex >= numOfSections; fenceIndex--) {
      sideSize = fencedY[fenceIndex] - fencedY[fenceIndex - numOfSections]

      // sizes in Y larger than largest size in X are useless
      if (sideSize > maxSizeX) continue 

      // if this Y based sideSize has a match in X direction, update maxSide if needed
      if (sectionsX.has(sideSize) && sideSize > maxSide) maxSide = sideSize
    }
    // less sections can still produce result bc larger ones didn't match x
  }

  // areas grow too large for regular numbers
  const area = maxSide ? Number((BigInt(maxSide) ** 2n) % (10n ** 9n + 7n)) : -1
  return area
}

Python solution:
class Solution:
    def maximizeSquareArea(self, m: int, n: int, hFences: List[int], vFences: List[int]) -> int:
        
        hFences.extend([1,m])
        vFences.extend([1,n])
        hFences.sort()
        vFences.sort()
        ha = set()
        ha.add(m-1)
        mod = 10**9 + 7
        mx = -1
        for i in range(len(hFences)):
            for j in range(i+1,len(hFences)):
                ha.add(hFences[j]-hFences[i])

        for i in range(len(vFences)-1,-1,-1):
            for j in range(0,i+1):
                a = vFences[i]-vFences[j]
                if a in ha:
                    mx = max(mx, (a*a))
                    break
        
        if mx != -1:
            return mx % mod
        return mx

Ruby solution:
def maximize_square_area(m, n, h_fences, v_fences)
    mod = 10**9 + 7

    # Process horizontal fences
    h = h_fences.dup
    h.push(1, m)
    h.sort!
    h_set = Set.new
    (0...h.size).each do |i|
        (i+1...h.size).each do |j|
            h_set.add(h[j] - h[i])
        end
    end

    # Process vertical fences
    v = v_fences.dup
    v.push(1, n)
    v.sort!
    v_set = Set.new
    (0...v.size).each do |i|
        (i+1...v.size).each do |j|
            v_set.add(v[j] - v[i])
        end
    end

    # Find the maximum common value
    common = h_set & v_set
    return -1 if common.empty?

    max_side = common.max
    (max_side * max_side) % mod
end