LeetCode 2975: Maximum Square Area by Removing Fences From a Field Solution

Master LeetCode problem 2975 (Maximum Square Area by Removing Fences From a Field), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2975. Maximum Square Area by Removing Fences From a Field

Medium

Array Hash Table Enumeration

Problem Explanation

Explanation

To solve this problem, we can iterate through all possible sizes of squares starting from the largest possible size down to 1. For each size, we check if we can form a square of that size by removing fences. We can use binary search to find the maximum possible square size that can be formed.

Initialize the left pointer as 1 and the right pointer as the minimum of m and n.
Perform a binary search to find the maximum square size where we can form a square.
For each iteration of the binary search, we check if it's possible to form a square of that size by removing fences.
If a square can be formed, update the left pointer to mid + 1. Otherwise, update the right pointer to mid - 1.
Finally, return the maximum area of the square found modulo 10^9 + 7.

Time Complexity: O(log(min(m, n)) * (hFences.length + vFences.length)) Space Complexity: O(hFences.length + vFences.length)

Solution Code

class Solution {
    public int maxArea(int m, int n, int[] hFences, int[] vFences) {
        int mod = 1000000007;
        Arrays.sort(hFences);
        Arrays.sort(vFences);

        int left = 1, right = Math.min(m, n);
        int res = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canFormSquare(mid, m, n, hFences, vFences)) {
                res = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return res == -1 ? -1 : res * res % mod;
    }

    private boolean canFormSquare(int size, int m, int n, int[] hFences, int[] vFences) {
        int hCount = countFencesWithin(size, m, hFences);
        int vCount = countFencesWithin(size, n, vFences);
        return hCount >= size && vCount >= size;
    }

    private int countFencesWithin(int size, int length, int[] fences) {
        int count = 0;
        int start = 0;
        for (int fence : fences) {
            if (fence - start >= size) {
                count += (fence - start) / size;
            }
            start = fence + 1;
        }
        if (length - start >= size) {
            count += (length - start) / size;
        }
        return count;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2975 (Maximum Square Area by Removing Fences From a Field)?

This page provides optimized solutions for LeetCode problem 2975 (Maximum Square Area by Removing Fences From a Field) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2975 (Maximum Square Area by Removing Fences From a Field)?

The time complexity for LeetCode 2975 (Maximum Square Area by Removing Fences From a Field) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2975 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2975 in Java, C++, or Python.

Back to LeetCode Solutions