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^91 <= hFences.length, vFences.length <= 6001 < hFences[i] < m1 < vFences[i] < nhFences and vFences contain unique values
Hints for Maximum Square Area by Removing Fences From a Field
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.
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.
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 + 7with 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
- Add the boundaries: horizontal positions
H = hFences + [1, m], vertical positionsV = vFences + [1, n]. - Insert every difference
|H[i] - H[j]|(i < j) into a hash set. - For every difference
dof two vertical positions, ifdis in the set, updatebest = max(best, d). - Return
-1if nothing matched, otherwisebest · 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(orn) misses the spans that use the edges of the field. dcan be close to 10^9, sod · doverflows 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 % 1000000007Java
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