Maximum Square Area by Removing Fences From a Field

Medium
1810.

Maximum Square Area by Removing Fences From a Field

Maximum Square Area by Removing Fences From a Field is a medium coding problem on arrays, hash table and enumeration, asked in Google interviews.

A rectangular field spans from corner (1, 1) to corner (m, n). Inside it run horizontal fences at the rows listed in hFences (a fence at hFences[i] goes from (hFences[i], 1) to (hFences[i], n)) and vertical fences at the columns listed in vFences (from (1, vFences[i]) to (m, vFences[i])). The field is also enclosed by four boundary fences — at rows 1 and m and columns 1 and n — which cannot be removed.

You may remove any of the inner fences. Return the maximum area of a square region bounded by fences that you can obtain, modulo 10^9 + 7, or -1 if no square can be formed.

Example 1

Input
m = 4, n = 3, hFences = [2,3], vFences = [2]
Output
4
Explanation
Removing the horizontal fence at 2 leaves a region from row 1 to row 3 and column 1 to column 3: a 2 × 2 square.

Example 2

Input
m = 6, n = 7, hFences = [2], vFences = [4]
Output
-1
Explanation
Horizontal spans available are 1, 4 and 5; vertical spans are 3, 3 and 6 — none in common.

Example 3

Input
m = 3, n = 3, hFences = [2], vFences = [2]
Output
4
Explanation
Remove both fences and the whole 2 × 2 field is a square.

Constraints

  • 3 <= m, n <= 10^9
  • 1 <= hFences.length, vFences.length <= 600
  • 1 < hFences[i] < m
  • 1 < vFences[i] < n
  • hFences and vFences contain unique values
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} m
 * @param {number} n
 * @param {number[]} hFences
 * @param {number[]} vFences
 * @return {number}
 */
var maximizeSquareArea = function(m, n, hFences, vFences) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Square Area by Removing Fences From a Field Solution

Maximum Square Area by Removing Fences From a Field solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Maximum Square Area by Removing Fences From a Field is a medium coding problem on arrays, hash table and enumeration, asked in Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table, Enumeration
  • Asked at: Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A rectangular field spans from corner (1, 1) to corner (m, n). Inside it run horizontal fences at the rows listed in hFences (a fence at hFences[i] goes from (hFences[i], 1) to (hFences[i], n)) and vertical fences at the columns listed in vFences (from (1, vFences[i]) to (m, vFences[i])). The field is also enclosed by four boundary fences — at rows 1 and m and columns 1 and n — which cannot be removed.

You may remove any of the inner fences. Return the maximum area of a square region bounded by fences that you can obtain, modulo 10^9 + 7, or -1 if no square can be formed.

Example 1

Input: m = 4, n = 3, hFences = [2,3], vFences = [2]
Output: 4
Explanation: Removing the horizontal fence at 2 leaves a region from row 1 to row 3 and column 1 to column 3: a 2 × 2 square.

Example 2

Input: m = 6, n = 7, hFences = [2], vFences = [4]
Output: -1
Explanation: Horizontal spans available are 1, 4 and 5; vertical spans are 3, 3 and 6 — none in common.

Example 3

Input: m = 3, n = 3, hFences = [2], vFences = [2]
Output: 4
Explanation: Remove both fences and the whole 2 × 2 field is a square.

Constraints

  • 3 <= m, n <= 10^9
  • 1 <= hFences.length, vFences.length <= 600
  • 1 < hFences[i] < m
  • 1 < vFences[i] < n
  • hFences and vFences contain unique values

Hints for Maximum Square Area by Removing Fences From a Field

  1. Hint 1

    A region bounded by fences is chosen by picking two horizontal fences (including the boundaries) and two vertical fences. Its sides are the differences between the picked positions.

  2. Hint 2

    A square needs a horizontal span equal to a vertical span. With at most 602 positions per direction there are at most about 180,000 spans of each kind.

  3. Hint 3

    Put every horizontal span into a hash set, scan every vertical span, and keep the largest one present in the set. Square it modulo 10^9 + 7 with 64-bit arithmetic.

How to solve Maximum Square Area by Removing Fences From a Field

Removing fences lets any two remaining horizontal positions bound a region, so the achievable heights are exactly the pairwise differences of {1, m} ∪ hFences, and likewise for widths. The answer is the largest value achievable both ways, squared.

Approach

  1. Add the boundaries: horizontal positions H = hFences + [1, m], vertical positions V = vFences + [1, n].
  2. Insert every difference |H[i] - H[j]| (i < j) into a hash set.
  3. For every difference d of two vertical positions, if d is in the set, update best = max(best, d).
  4. Return -1 if nothing matched, otherwise best · best mod (10^9 + 7).

Why it works

For any two horizontal positions a < b you can remove every horizontal fence strictly between them (and keep them), so a height of b - a is available; vertical fences are independent. Conversely, every bounded region's height is such a difference. So a square of side d exists iff d is both a horizontal and a vertical difference, and the largest common one gives the largest area.

Complexity

  • Time — O(h^2 + v^2)
  • Space — O(h^2)

Pitfalls

  • Forgetting the boundary fences at 1 and m (or n) misses the spans that use the edges of the field.
  • d can be close to 10^9, so d · d overflows 32 bits — and a JavaScript double is not exact at 10^18; split the multiplication.
  • Take the maximum before reducing modulo 10^9 + 7; comparing reduced areas is wrong.

Reference solution

Python

from typing import List

def maximizeSquareArea(m: int, n: int, hFences: List[int], vFences: List[int]) -> int:
    h = hFences + [1, m]
    v = vFences + [1, n]
    spans = {abs(a - b) for i, a in enumerate(h) for b in h[i + 1:]}
    best = -1
    for i, a in enumerate(v):
        for b in v[i + 1:]:
            d = abs(a - b)
            if d > best and d in spans:
                best = d
    return -1 if best < 0 else best * best % 1000000007

Java

public static int maximizeSquareArea(int m, int n, int[] hFences, int[] vFences) {
    int[] h = Arrays.copyOf(hFences, hFences.length + 2);
    h[hFences.length] = 1;
    h[hFences.length + 1] = m;
    int[] v = Arrays.copyOf(vFences, vFences.length + 2);
    v[vFences.length] = 1;
    v[vFences.length + 1] = n;
    HashSet<Integer> spans = new HashSet<>();
    for (int i = 0; i < h.length; i++)
        for (int j = i + 1; j < h.length; j++) spans.add(Math.abs(h[i] - h[j]));
    int best = -1;
    for (int i = 0; i < v.length; i++)
        for (int j = i + 1; j < v.length; j++) {
            int d = Math.abs(v[i] - v[j]);
            if (d > best && spans.contains(d)) best = d;
        }
    if (best < 0) return -1;
    return (int) ((long) best * best % 1000000007L);
}

C++

int maximizeSquareArea(int m, int n, vector<int>& hFences, vector<int>& vFences) {
    vector<int> h(hFences), v(vFences);
    h.push_back(1); h.push_back(m);
    v.push_back(1); v.push_back(n);
    unordered_set<int> spans;
    for (size_t i = 0; i < h.size(); i++)
        for (size_t j = i + 1; j < h.size(); j++) spans.insert(abs(h[i] - h[j]));
    int best = -1;
    for (size_t i = 0; i < v.size(); i++)
        for (size_t j = i + 1; j < v.size(); j++) {
            int d = abs(v[i] - v[j]);
            if (d > best && spans.count(d)) best = d;
        }
    if (best < 0) return -1;
    return (int) ((long long) best * best % 1000000007LL);
}

JavaScript

var maximizeSquareArea = function(m, n, hFences, vFences) {
    var h = hFences.concat([1, m]), v = vFences.concat([1, n]);
    var spans = new Set();
    for (var i = 0; i < h.length; i++)
        for (var j = i + 1; j < h.length; j++) spans.add(Math.abs(h[i] - h[j]));
    var best = -1;
    for (var p = 0; p < v.length; p++)
        for (var q = p + 1; q < v.length; q++) {
            var d = Math.abs(v[p] - v[q]);
            if (d > best && spans.has(d)) best = d;
        }
    if (best < 0) return -1;
    // best * best overflows a double's exact range: multiply in two halves.
    var MOD = 1000000007;
    var hi = (best * Math.floor(best / 32768)) % MOD;
    return (hi * 32768 + best * (best % 32768)) % MOD;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets