Maximize Area of Square Hole in Grid
MedPrompt
You are given the two integers, n and m and two integer arrays, hBars and vBars. The grid has n + 2 horizontal and m + 2 vertical bars, creating 1 x 1 unit cells. The bars are indexed starting from 1.
You can remove some of the bars in hBars from horizontal bars and some of the bars in vBars from vertical bars. Note that other bars are fixed and cannot be removed.
Return an integer denoting the maximum area of a square-shaped hole in the grid, after removing some bars (possibly none).
Example 1:
Input: n = 2, m = 1, hBars = [2,3], vBars = [2]
Output: 4
Explanation:
The left image shows the initial grid formed by the bars. The horizontal bars are [1,2,3,4], and the vertical bars are [1,2,3].
One way to get the maximum square-shaped hole is by removing horizontal bar 2 and vertical bar 2.
Example 2:
Input: n = 1, m = 1, hBars = [2], vBars = [2]
Output: 4
Explanation:
To get the maximum square-shaped hole, we remove horizontal bar 2 and vertical bar 2.
Example 3:
Input: n = 2, m = 3, hBars = [2,3], vBars = [2,4]
Output: 4
Explanation:
One way to get the maximum square-shaped hole is by removing horizontal bar 3, and vertical bar 4.
Constraints:
1 <= n <= 1091 <= m <= 1091 <= hBars.length <= 1002 <= hBars[i] <= n + 11 <= vBars.length <= 1002 <= vBars[i] <= m + 1- All values in
hBarsare distinct. - All values in
vBarsare distinct.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach iterates through all possible side lengths for the square hole, from largest to smallest. For each side length s, it checks if it's possible to create such a hole. This requires finding a contiguous block of s-1 removable horizontal bars and s-1 removable vertical bars. The check for these consecutive sequences is done by naively iterating through the hBars and vBars arrays in a nested loop fashion.
Algorithm
- Iterate
sfrommin(hBars.length, vBars.length) + 1down to 1. - For each
s, letk = s - 1. - Define a helper function
hasConsecutive(bars, k):- For each
startBarinbars:- Assume a sequence is found.
- For
ifrom 1 tok-1, check ifstartBar + iexists inbarsby iterating throughbarsagain. - If any element is not found, this is not a valid sequence from
startBar. - If all
k-1elements are found, returntrue.
- If the loop finishes, return
false.
- For each
- Call
hasConsecutiveforhBarsandvBarswithk. - If both calls return
true, we have found the maximum sides. Returns * s. - If the loop finishes, it means the maximum side is 1. Return 1.
Walkthrough
The main idea is to determine the maximum possible side length, s, and then calculate the area as s*s.
We can iterate on s from a maximum possible value down to 1. The first s for which a square hole is possible will be our answer. The maximum possible side length is limited by the number of removable bars, so we can start iterating from min(hBars.length, vBars.length) + 1.
For a given side s, we need to check if there exist s-1 consecutive removable bars in both hBars and vBars. We create a helper function, hasConsecutive(bars, k), which checks if the array bars contains a sequence of k consecutive integers.
This helper function works by taking each element b from bars as a potential start of a sequence and then checking if b+1, b+2, ..., b+k-1 are also present in bars. This inner check involves another loop through the bars array, leading to a high time complexity.
The first s that satisfies the condition for both hBars and vBars gives the maximum side length. If no such s > 1 is found, the answer is a 1x1 hole (area 1), which is always possible.
class Solution { private boolean hasConsecutive(int[] bars, int k) { if (k == 0) return true; if (k > bars.length) return false; for (int startBar : bars) { boolean foundSequence = true; for (int i = 1; i < k; i++) { int nextBar = startBar + i; boolean foundNext = false; for (int bar : bars) { if (bar == nextBar) { foundNext = true; break; } } if (!foundNext) { foundSequence = false; break; } } if (foundSequence) { return true; } } return false; } public int maximizeSquareHoleArea(int n, int m, int[] hBars, int[] vBars) { int maxPossibleSide = Math.min(hBars.length, vBars.length) + 1; for (int s = maxPossibleSide; s >= 1; s--) { if (hasConsecutive(hBars, s - 1) && hasConsecutive(vBars, s - 1)) { long side = s; return (int)(side * side); } } return 0; // Should be unreachable }}Complexity
Time
O(S^2 * (L_h^2 + L_v^2)). Here, L_h and L_v are the lengths of the bar arrays, and S is the maximum possible side length (`min(L_h, L_v) + 1`). Given the constraints, this is too slow.
Space
O(1), as no additional data structures are used that scale with the input size.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space besides the input arrays.
Cons
Very inefficient due to multiple nested loops.
Likely to result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
This approach improves upon the brute-force method. It still iterates through possible side lengths s from high to low. However, the check for a consecutive sequence of length s-1 is significantly optimized. Instead of nested loops for searching, we use a Hash Set for O(1) average time lookups, which makes the check much faster.
Algorithm
- Iterate
sfrommin(hBars.length, vBars.length) + 1down to 1. - For each
s, letk = s - 1. - Define an optimized helper function
hasConsecutive(bars, k):- Create a
HashSetand add all elements frombarsto it. - For each
barin the set:- If
bar - 1is not in the set, thisbaris the start of a potential sequence. - Count the length of the consecutive sequence starting from
bar. - If this length is
>= k, returntrue.
- If
- If the loop finishes, return
false.
- Create a
- Call this optimized
hasConsecutiveforhBarsandvBarswithk. - If both calls return
true, returns * s. - If the loop finishes, return 1.
Walkthrough
The overall structure is the same as the brute-force approach: find the largest side s that works by iterating s downwards.
The key improvement is in the hasConsecutive(bars, k) helper function. This function is made much more efficient:
- First, we insert all elements of the
barsarray into aHashSet. This takesO(L)time, whereLis the length of the array. - Then, to check if a sequence of at least length
kexists, we iterate through each unique barbin the hash set. - For each
b, we check if it's the start of a sequence by verifying thatb-1is not in the set. This avoids redundant checks. - If
bis a starting point, we count how long the consecutive sequence is by repeatedly checking forb+1, b+2, ...in the hash set. - If the length of any found sequence is greater than or equal to
k, we can immediately returntrue. - If we check all possible starting points and none yield a sequence of length
k, we returnfalse.
This optimized check function runs in O(L) time because each bar is visited a constant number of times in total. This makes the overall approach feasible within the time limits.
import java.util.HashSet;import java.util.Set; class Solution { private boolean hasConsecutive(int[] bars, int k) { if (k == 0) return true; if (k > bars.length) return false; Set<Integer> barSet = new HashSet<>(); for (int bar : bars) { barSet.add(bar); } for (int bar : barSet) { // Check if it's the start of a sequence to avoid redundant work if (!barSet.contains(bar - 1)) { int count = 1; while (barSet.contains(bar + count)) { count++; } if (count >= k) { return true; } } } return false; } public int maximizeSquareHoleArea(int n, int m, int[] hBars, int[] vBars) { int maxPossibleSide = Math.min(hBars.length, vBars.length) + 1; for (int s = maxPossibleSide; s >= 1; s--) { if (hasConsecutive(hBars, s - 1) && hasConsecutive(vBars, s - 1)) { long side = s; return (int)(side * side); } } return 0; // Should be unreachable }}Complexity
Time
O(S * (L_h + L_v)), where S is the max possible side length (`min(L_h, L_v) + 1`), and L_h, L_v are array lengths. This is efficient enough for the given constraints.
Space
O(L_h + L_v) to store the hash sets. Since the checks are sequential, the peak space usage is O(max(L_h, L_v)).
Trade-offs
Pros
Much faster than the naive brute-force check.
Feasible for the given constraints.
Conceptually still follows a simple search-and-verify pattern.
Cons
Not the most optimal solution as it might perform redundant computations across different values of
s.Uses extra space for the hash sets.
This is the most efficient approach. Instead of checking for each possible side length, we can directly calculate the maximum possible side for the hole. The side of a square hole is determined by the smaller of the maximum possible height and maximum possible width. The maximum height (or width) is created by removing the longest possible sequence of consecutive bars.
Algorithm
- Create a helper function
findMaxConsecutive(bars)that finds the length of the longest sequence of consecutive numbers in an array. - Inside
findMaxConsecutive(bars):- Handle the edge case of an empty array (return 0).
- Sort the
barsarray. - Initialize
maxLength = 1andcurrentLength = 1. - Iterate through the sorted array from the second element (
i=1). - If
bars[i] == bars[i-1] + 1, the numbers are consecutive, so incrementcurrentLength. - If they are not consecutive (i.e.,
bars[i] > bars[i-1] + 1), the sequence is broken, so resetcurrentLengthto 1. - After each element, update
maxLength = max(maxLength, currentLength). - Return
maxLength.
- In the main function, calculate
max_h_consecutive = findMaxConsecutive(hBars). - Calculate
max_v_consecutive = findMaxConsecutive(vBars). - The side of the largest square is
side = min(max_h_consecutive + 1, max_v_consecutive + 1). - Return
side * side.
Walkthrough
The core insight is that a hole of side s requires removing s-1 consecutive horizontal bars and s-1 consecutive vertical bars. To maximize s, we must therefore find the longest possible run of consecutive removable bars for both horizontal and vertical directions.
- Let
max_h_consecutivebe the length of the longest run of consecutive integers inhBars. By removing these bars, we can create a hole with a maximum height ofmax_h_consecutive + 1. - Similarly, let
max_v_consecutivebe the length of the longest run of consecutive integers invBars. This allows for a maximum width ofmax_v_consecutive + 1.
The side of the largest square hole is limited by the smaller of these two dimensions. Therefore, the maximum side length is side = min(max_h_consecutive + 1, max_v_consecutive + 1).
The final answer is the area, side * side.
To find the longest run of consecutive integers in an array, a simple and efficient method is to first sort the array. Then, a single pass through the sorted array is sufficient to find the longest consecutive sequence.
import java.util.Arrays; class Solution { private int findMaxConsecutive(int[] bars) { if (bars.length == 0) { return 0; } Arrays.sort(bars); int maxLength = 1; int currentLength = 1; for (int i = 1; i < bars.length; i++) { // Since bars are distinct, we only need to check for +1 if (bars[i] == bars[i - 1] + 1) { currentLength++; } else { // Sequence is broken, reset currentLength = 1; } maxLength = Math.max(maxLength, currentLength); } return maxLength; } public int maximizeSquareHoleArea(int n, int m, int[] hBars, int[] vBars) { int maxHConsecutive = findMaxConsecutive(hBars); int maxVConsecutive = findMaxConsecutive(vBars); // A gap of k consecutive removed bars creates a hole of side k+1 long side = Math.min(maxHConsecutive + 1, maxVConsecutive + 1); return (int)(side * side); }}Complexity
Time
O(L_h log L_h + L_v log L_v), where L_h and L_v are the lengths of the input arrays. This is dominated by the sorting step.
Space
O(log L) or O(L), depending on the implementation of the sorting algorithm. For Java's `Arrays.sort` on primitive types, the space complexity is O(log L) on average.
Trade-offs
Pros
Most efficient time complexity.
Directly computes the required values without searching.
The logic is straightforward once the problem is reduced to finding the longest consecutive sequence.
Cons
The time complexity is bound by sorting, which is not linear time.
Solutions
Solution
class Solution {public int maximizeSquareHoleArea(int n, int m, int[] hBars, int[] vBars) { int x = Math.min(f(hBars), f(vBars)); return x * x; }private int f(int[] nums) { Arrays.sort(nums); int ans = 1, cnt = 1; for (int i = 1; i < nums.length; ++i) { if (nums[i] == nums[i - 1] + 1) { ans = Math.max(ans, ++cnt); } else { cnt = 1; } } return ans + 1; }}class Solution: def maximizeSquareHoleArea(self, n: int, m: int, hBars: List[int], vBars: List[int]) -> int: def f(nums: List[int]) -> int: nums . sort() ans = cnt = 1 for i in range(1, len(nums)): if nums[i] == nums[i - 1] + 1: cnt += 1 ans = max(ans, cnt) else: cnt = 1 return ans + 1 return min(f(hBars), f(vBars)) ** 2class Solution {public: int maximizeSquareHoleArea(int n, int m, vector<int> &hBars, vector<int> &vBars) { auto f = [](vector<int> &nums) { int ans = 1, cnt = 1; sort(nums.begin(), nums.end()); for (int i = 1; i < nums.size(); ++i) { if (nums[i] == nums[i - 1] + 1) { ans = max(ans, ++cnt); } else { cnt = 1; } } return ans + 1; }; int x = min(f(hBars), f(vBars)); return x * x; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.