Maximize Area of Square Hole in Grid
Maximize Area of Square Hole in Grid is a medium arrays & hashing problem solved with the hash set lookup pattern.
The best approach, optimal (sort and find the longest consecutive run), runs in O(L log L) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (extend each run by searching) up.
Problem
Picture a grid drawn with n + 2 horizontal bars and m + 2 vertical bars, numbered from 1, that cut the plane into (n + 1) x (m + 1) unit cells.
The arrays hBars and vBars list the horizontal and vertical bars you are allowed to remove; every other bar is fixed. You may remove any subset of the allowed bars (or none).
Return the largest area of a square hole you can create in the grid this way.
Examples
Example 1
- Input
n = 5, m = 6, hBars = [5, 2, 3, 4], vBars = [3, 6, 4]- Output
9- Why
- Removing horizontal bars 2-5 opens a gap of height 5, and removing vertical bars 3 and 4 opens a gap of width 3. The biggest square fits in the smaller one: 3 x 3 = 9.
Example 2
- Input
n = 1, m = 1, hBars = [2], vBars = [2]- Output
4- Why
- Removing the middle bar in both directions turns the 2 x 2 grid of cells into one 2 x 2 hole.
Example 3
- Input
n = 4, m = 7, hBars = [3], vBars = [2, 3, 4, 5]- Output
4- Why
- Vertically we could open a gap of width 5, but horizontally the best gap is 2, so the square is 2 x 2.
Constraints
1 <= n, m <= 10^91 <= hBars.length, vBars.length <= 1002 <= hBars[i] <= n + 1and2 <= vBars[i] <= m + 1- The values in
hBarsare distinct, and so are the values invBars.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (extend each run by searching) | O(L³) | O(1) |
| Optimal (sort and find the longest consecutive run) | O(L log L) | O(1) |
1Brute force (extend each run by searching)
O(L³)For each of L bars a run can grow up to L steps, and each step scans the array of length L.O(1)Only counters.The two directions are independent. In one direction, removing bars b, b + 1, ..., b + k - 1 opens a gap of k + 1. For every bar, count how far the run b, b + 1, b + 2, ... continues by searching the array for each next value. The longest run plus one is the best gap; the square side is the smaller gap of the two directions.
- For each bar b in the array, set len = 1 and keep checking (with a linear scan) whether b + len is also in the array; increase len while it is.
- The best gap for that direction is the maximum len plus one.
- Do this for hBars and vBars; side = min of the two gaps; return side * side.
class Solution {
public int maximizeSquareHoleArea(int n, int m, int[] hBars, int[] vBars) {
int side = Math.min(bestGap(hBars), bestGap(vBars));
return side * side;
}
private int bestGap(int[] bars) {
int longest = 0;
for (int b : bars) {
int len = 1;
while (contains(bars, b + len)) len++;
longest = Math.max(longest, len);
}
return longest + 1;
}
private boolean contains(int[] bars, int value) {
for (int x : bars) {
if (x == value) return true;
}
return false;
}
}class Solution:
def maximizeSquareHoleArea(self, n: int, m: int, hBars: List[int], vBars: List[int]) -> int:
side = min(self.best_gap(hBars), self.best_gap(vBars))
return side * side
def best_gap(self, bars: List[int]) -> int:
longest = 0
for b in bars:
length = 1
while self.contains(bars, b + length):
length += 1
longest = max(longest, length)
return longest + 1
def contains(self, bars: List[int], value: int) -> bool:
for x in bars:
if x == value:
return True
return Falseclass Solution {
public:
int maximizeSquareHoleArea(int n, int m, vector<int>& hBars, vector<int>& vBars) {
int side = min(bestGap(hBars), bestGap(vBars));
return side * side;
}
private:
int bestGap(vector<int>& bars) {
int longest = 0;
for (int b : bars) {
int len = 1;
while (contains(bars, b + len)) len++;
longest = max(longest, len);
}
return longest + 1;
}
bool contains(vector<int>& bars, int value) {
for (int x : bars) {
if (x == value) return true;
}
return false;
}
};function maximizeSquareHoleArea(n, m, hBars, vBars) {
const side = Math.min(bestGap(hBars), bestGap(vBars));
return side * side;
}
function bestGap(bars) {
let longest = 0;
for (const b of bars) {
let len = 1;
while (contains(bars, b + len)) len++;
longest = Math.max(longest, len);
}
return longest + 1;
}
function contains(bars, value) {
for (const x of bars) {
if (x === value) return true;
}
return false;
}2Optimal (sort and find the longest consecutive run)
O(L log L)Sorting dominates; the scans are linear. L is the length of the longer array.O(1)Sorting in place plus a few counters (ignoring the sort's internal stack).Sort each array. Consecutive bar numbers now sit next to each other, so one pass finds the longest run where each value is exactly one more than the previous. A run of length k opens a gap of k + 1. The square side is the smaller gap of the two directions, and the area is its square.
- Sort hBars and vBars.
- Scan each sorted array: if bars[i] == bars[i - 1] + 1, extend the current run, otherwise restart it at 1; track the longest run.
- gap = longest run + 1 for each direction; side = min(gapH, gapV).
- Return side * side.
class Solution {
public int maximizeSquareHoleArea(int n, int m, int[] hBars, int[] vBars) {
int side = Math.min(bestGap(hBars), bestGap(vBars));
return side * side;
}
private int bestGap(int[] bars) {
Arrays.sort(bars);
int longest = 1, run = 1;
for (int i = 1; i < bars.length; i++) {
run = bars[i] == bars[i - 1] + 1 ? run + 1 : 1;
longest = Math.max(longest, run);
}
return longest + 1;
}
}class Solution:
def maximizeSquareHoleArea(self, n: int, m: int, hBars: List[int], vBars: List[int]) -> int:
side = min(self.best_gap(hBars), self.best_gap(vBars))
return side * side
def best_gap(self, bars: List[int]) -> int:
bars = sorted(bars)
longest = run = 1
for i in range(1, len(bars)):
run = run + 1 if bars[i] == bars[i - 1] + 1 else 1
longest = max(longest, run)
return longest + 1class Solution {
public:
int maximizeSquareHoleArea(int n, int m, vector<int>& hBars, vector<int>& vBars) {
int side = min(bestGap(hBars), bestGap(vBars));
return side * side;
}
private:
int bestGap(vector<int>& bars) {
sort(bars.begin(), bars.end());
int longest = 1, run = 1;
for (size_t i = 1; i < bars.size(); i++) {
run = bars[i] == bars[i - 1] + 1 ? run + 1 : 1;
longest = max(longest, run);
}
return longest + 1;
}
};function maximizeSquareHoleArea(n, m, hBars, vBars) {
const side = Math.min(bestGap(hBars), bestGap(vBars));
return side * side;
}
function bestGap(bars) {
bars.sort((a, b) => a - b);
let longest = 1, run = 1;
for (let i = 1; i < bars.length; i++) {
run = bars[i] === bars[i - 1] + 1 ? run + 1 : 1;
longest = Math.max(longest, run);
}
return longest + 1;
}Edge cases to test
- Only one removable bar in a direction: the best gap there is 2
- Removable bars that are not consecutive, so each removal only gives a gap of 2
- Unsorted input
- One direction allows a much larger gap than the other; the smaller one limits the square
Hints
Hint 1
Removing a single bar merges the two cells on either side into a gap of 2. When do removals combine into a bigger gap?
Hint 2
Removing k bars with consecutive numbers merges k + 1 unit rows into one gap of size k + 1.
Hint 3
Find the longest run of consecutive numbers in each array. The square side is the smaller of the two run lengths plus one.
FAQ
What is the best time complexity for Maximize Area of Square Hole in Grid?
Optimal (sort and find the longest consecutive run) runs in O(L log L) time and O(1) extra space. Sorting dominates; the scans are linear. L is the length of the longer array.
Which pattern does Maximize Area of Square Hole in Grid use?
It is a arrays & hashing problem that uses the hash set lookup pattern. Other problems with the same pattern: Longest Consecutive Sequence, Contains Duplicate, Fair Candy Swap.
Is there a brute force solution for Maximize Area of Square Hole in Grid?
Yes. Brute force (extend each run by searching) takes O(L³) time and O(1) space. The two directions are independent.
Which edge cases should I test for Maximize Area of Square Hole in Grid?
Only one removable bar in a direction: the best gap there is 2; Removable bars that are not consecutive, so each removal only gives a gap of 2; Unsorted input; One direction allows a much larger gap than the other; the smaller one limits the square.