2975. Maximum Square Area by Removing Fences Solution

Q: 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.

Q: 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).

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

The 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 10⁹+ 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 <= 10⁹
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.

Python

def max_square_area(m, n, h_fences, v_fences):
    MOD = 10**9 + 7
    h_fences = [0] + sorted(h_fences) + [m]
    v_fences = [0] + sorted(v_fences) + [n]

    max_height = max(h_fences[i] - h_fences[i - 1] for i in range(1, len(h_fences)))
    max_width = max(v_fences[i] - v_fences[i - 1] for i in range(1, len(v_fences)))

    return (max_height * max_width) % MOD

if __name__ == "__main__":
    m = 4
    n = 3
    h_fences = [2, 3]
    v_fences = [2]
    print(max_square_area(m, n, h_fences, v_fences))

Java

import java.util.Arrays;

public class MaxSquareArea {
    private static final int MOD = 1000000007;

    public static int maxSquareArea(int m, int n, int[] hFences, int[] vFences) {
        Arrays.sort(hFences);
        Arrays.sort(vFences);

        int maxHeight = Math.max(hFences[0], m - hFences[hFences.length - 1]);
        for (int i = 1; i < hFences.length; i++) {
            maxHeight = Math.max(maxHeight, hFences[i] - hFences[i - 1]);
        }

        int maxWidth = Math.max(vFences[0], n - vFences[vFences.length - 1]);
        for (int i = 1; i < vFences.length; i++) {
            maxWidth = Math.max(maxWidth, vFences[i] - vFences[i - 1]);
        }

        long result = (long) maxHeight * maxWidth % MOD;
        return (int) result;
    }

    public static void main(String[] args) {
        int m = 4, n = 3;
        int[] hFences = {2, 3};
        int[] vFences = {2};
        System.out.println(maxSquareArea(m, n, hFences, vFences));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
#define MOD 1000000007

using namespace std;

long long maxSquareArea(int m, int n, vector<int>& hFences, vector<int>& vFences) {
    hFences.push_back(0);
    hFences.push_back(m);
    vFences.push_back(0);
    vFences.push_back(n);
    
    sort(hFences.begin(), hFences.end());
    sort(vFences.begin(), vFences.end());
    
    int maxHeight = 0, maxWidth = 0;
    for (size_t i = 1; i < hFences.size(); ++i) {
        maxHeight = max(maxHeight, hFences[i] - hFences[i - 1]);
    }
    for (size_t i = 1; i < vFences.size(); ++i) {
        maxWidth = max(maxWidth, vFences[i] - vFences[i - 1]);
    }
    return (1LL * maxHeight * maxWidth) % MOD;
}

int main() {
    int m = 4, n = 3;
    vector<int> hFences = {2, 3};
    vector<int> vFences = {2};

    cout << maxSquareArea(m, n, hFences, vFences) << endl;
    return 0;
}

JavaScript

function maxSquareArea(m, n, hFences, vFences) {
    const MOD = 1000000007;
    hFences.sort((a, b) => a - b);
    vFences.sort((a, b) => a - b);

    let maxHeight = Math.max(hFences[0], m - hFences[hFences.length - 1]);
    for (let i = 1; i < hFences.length; i++) {
        maxHeight = Math.max(maxHeight, hFences[i] - hFences[i - 1]);
    }

    let maxWidth = Math.max(vFences[0], n - vFences[vFences.length - 1]);
    for (let i = 1; i < vFences.length; i++) {
        maxWidth = Math.max(maxWidth, vFences[i] - vFences[i - 1]);
    }

    const result = (BigInt(maxHeight) * BigInt(maxWidth)) % BigInt(MOD);
    return parseInt(result.toString(), 10);
}

console.log(maxSquareArea(4, 3, [2, 3], [2]));

#include <stdio.h>
#include <stdlib.h>
#define MOD 1000000007

int max(int a, int b) {
    return a > b ? a : b;
}

void sort(int *arr, int size) {
    qsort(arr, size, sizeof(int), (int (*)(const void *, const void *))strcmp);
}

int maxSquareArea(int m, int n, int *hFences, int hSize, int *vFences, int vSize) {
    int maxHeight = 0, maxWidth = 0;
    int prev = 0;
    
    sort(hFences, hSize);
    sort(vFences, vSize);

    for (int i = 0; i < hSize; i++) {
        maxHeight = max(maxHeight, hFences[i] - prev);
        prev = hFences[i];
    }
    maxHeight = max(maxHeight, m - prev);

    prev = 0;
    for (int i = 0; i < vSize; i++) {
        maxWidth = max(maxWidth, vFences[i] - prev);
        prev = vFences[i];
    }
    maxWidth = max(maxWidth, n - prev);

    long long result = ((long long) maxHeight * maxWidth) % MOD;
    return (int) result;
}

int main() {
    int m = 4, n = 3;
    int hFences[] = {2, 3};
    int vFences[] = {2};

    printf("%d\n", maxSquareArea(m, n, hFences, 2, vFences, 1));
    return 0;
}

using System;
using System.Linq;

public class Solution {
    private const int MOD = 1000000007;

    public int MaxSquareArea(int m, int n, int[] hFences, int[] vFences) {
        Array.Sort(hFences);
        Array.Sort(vFences);

        int maxHeight = Math.Max(hFences[0], m - hFences[hFences.Length - 1]);
        for (int i = 1; i < hFences.Length; i++) {
            maxHeight = Math.Max(maxHeight, hFences[i] - hFences[i - 1]);
        }

        int maxWidth = Math.Max(vFences[0], n - vFences[vFences.Length - 1]);
        for (int i = 1; i < vFences.Length; i++) {
            maxWidth = Math.Max(maxWidth, vFences[i] - vFences[i - 1]);
        }

        long result = (long)maxHeight * maxWidth % MOD;
        return (int)result;
    }

    public static void Main(string[] args) {
        int m = 4, n = 3;
        int[] hFences = {2, 3};
        int[] vFences = {2};
        Solution solution = new Solution();
        Console.WriteLine(solution.MaxSquareArea(m, n, hFences, vFences));
    }
}

In Python, the approach leverages slicing and list comprehensions to calculate the biggest consecutive gaps, adding external boundaries as potential fence locations, and then computing the maximal possible square area under modulo arithmetic.

Complexity

Time Complexity: O(k log k) due to sorting.
Space Complexity: O(1), excluding input lists.

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.

TypeScript

function maximizeSquareArea(m: number, n: number, hFences: number[], vFences: number[]): number {
    const f = (nums: number[], k: number): Set<number> => {
        nums.push(1, k);
        nums.sort((a, b) => a - b);
        const s: Set<number> = new Set();
        for (let i = 0; i < nums.length; ++i) {
            for (let j = 0; j < i; ++j) {
                s.add(nums[i] - nums[j]);
            }
        }
        return s;
    };
    const hs = f(hFences, m);
    const vs = f(vFences, n);
    let ans = 0;
    for (const h of hs) {
        if (vs.has(h)) {
            ans = Math.max(ans, h);
        }
    }
    return ans ? Number(BigInt(ans) ** 2n % 1000000007n) : -1;
}

func maximizeSquareArea(m int, n int, hFences []int, vFences []int) int {
	f := func(nums []int, k int) map[int]bool {
		nums = append(nums, 1, k)
		sort.Ints(nums)
		s := map[int]bool{}
		for i := 0; i < len(nums); i++ {
			for j := 0; j < i; j++ {
				s[nums[i]-nums[j]] = true
			}
		}
		return s
	}
	hs := f(hFences, m)
	vs := f(vFences, n)
	ans := 0
	for h := range hs {
		if vs[h] {
			ans = max(ans, h)
		}
	}
	if ans > 0 {
		return ans * ans % (1e9 + 7)
	}
	return -1
}

Rust

use std::collections::HashSet;

impl Solution {
    pub fn maximize_square_area(m: i32, n: i32, h_fences: Vec<i32>, v_fences: Vec<i32>) -> i32 {
        fn calc(mut nums: Vec<i32>, k: i32) -> HashSet<i32> {
            nums.push(k);
            nums.push(1);
            nums.sort_unstable();
            let mut s = HashSet::new();
            let len = nums.len();
            for i in 0..len {
                for j in 0..i {
                    s.insert(nums[i] - nums[j]);
                }
            }
            s
        }

        let hs = calc(h_fences, m);
        let vs = calc(v_fences, n);

        let mut ans = 0i64;
        for &h in hs.iter() {
            if vs.contains(&h) {
                ans = ans.max(h as i64);
            }
        }

        if ans > 0 {
            let modv = 1_000_000_007i64;
            ((ans * ans) % modv) as i32
        } else {
            -1
        }
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Approach	Time Complexity: O(k log k) due to sorting. Space Complexity: O(1), excluding input lists.
Enumeration	–

Complexity analysis

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

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.

Maximum Square Area by Removing Fences From a Field solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach

Approach 2: Enumeration

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Maximum Square Area by Removing Fences From a Field solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach

Approach 2: Enumeration

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems