Maximize Area of Square Hole in Grid solution and explanation
9 more videos on this problem
Maximize Area of Square Hole in Grid | Detailed Intuition | Leetcode 2943 | codestorywithMIKcodestorywithMIK · 27:54 · 9K views
Maximize Area of Square Hole in Grid | LeetCode 2943 | Optimal Approach Study Placement · 10:49 · 1K views
Maximize Area of Square Hole in Grid | LeetCode 2943 | Complate Intuition ExplainedSanyam IIT Guwahati · 23:25 · 1K views
2943. Maximize Area of Square Hole in Grid | Leetcode 2943 | BiWeekly Contest 118Tech Courses · 13:59 · 850 views
2943. Maximize Area of Square Hole in Grid | Leetcode Daily - PythonLeetcode Daily · 8:33 · 773 views
Daily Leetcode #2116: Jan 15, 2026 - 2943. Maximize Area of Square Hole in GridProgramming Live with Larry · 10:21 · 380 views
2943. Maximize Area of Square Hole in Grid (Leetcode Medium)Programming Live with Larry · 9:51 · 335 views
LeetCode Daily Challenge | Maximize Area of Square Hole in Grid (2943) | Greedy + Sorting ExplainedThe Boolean Brain · 19:12 · 174 views
Maximize Area of Square Hole in Grid - Leetcode 2943 - PythonTim Huang · 5:26 · 137 views
Maximize Area of Square Hole in Grid | LeetCode 2943 - Pythonimpoldev · 9:39 · 119 views
The problem
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.
Approach overview
Problem Overview: You are given horizontal and vertical bars removed from a grid. Removing consecutive bars creates a larger hole. The goal is to compute the maximum possible square area that can be formed from these removed bars.
Approach 1: Recursive Depth-First Search (DFS) Grid Exploration (Time: O(n*m), Space: O(n*m))
Model the grid as a matrix where removed bars create open cells. Starting from each open position, run a recursive DFS to explore connected regions. Track the largest square that can be formed inside that region by expanding while neighbors remain open. DFS repeatedly visits neighbors using recursion and marks cells as visited to avoid revisiting. This approach works conceptually but simulating the grid is expensive when the grid dimensions are large.
Approach 2: Iterative Breadth-First Search (BFS) Region Expansion (Time: O(n*m), Space: O(n*m))
Instead of recursion, use a queue-based BFS to explore open regions formed by removed bars. Push the starting cell into a queue and iteratively expand to neighbors. BFS processes cells layer by layer and records the width and height of reachable empty space. From this region size you compute the largest possible square. This approach avoids recursion depth limits and provides predictable memory usage, but it still requires explicitly constructing and traversing the grid.
Approach 3: Sorting Consecutive Bars (Optimal) (Time: O(k log k), Space: O(1))
The key observation: removing k consecutive horizontal bars creates a vertical gap of size k + 1. The same applies to vertical bars. Instead of exploring the grid, sort the removed bar indices and scan them to find the longest consecutive sequence. For example, if horizontal bars [2,3,4] are removed, the gap height becomes 4. Do this independently for horizontal and vertical arrays. The largest square side equals min(maxHorizontalGap, maxVerticalGap). The square area is that side squared.
This approach relies on simple array operations: sort, iterate once to count consecutive sequences, and track the maximum run length. No grid simulation is required. Because the logic operates only on the removed bar arrays, it scales well even when the grid size itself is very large.
Related concepts frequently appear in problems involving arrays and sorting, where ordering elements reveals structural patterns such as consecutive runs or gaps.
Recommended for interviews: The sorting-based approach is what interviewers typically expect. It shows you recognized the mathematical structure of consecutive bars rather than simulating the entire grid. Explaining the DFS or BFS idea first demonstrates problem exploration, but moving to the sort + consecutive scan solution shows strong optimization instincts.
Approach 1: Recursive Depth-First Search (DFS)
This approach utilizes a recursive DFS algorithm. DFS can efficiently explore possible solutions to problems like searching tree or graph structures. Through recursion, the algorithm will delve deep into each node before backtracking, making it suitable for problems requiring exploration of all potential paths.
def dfs_recursive(node, visited=set()):
if node is None:
return
if node not in visited:
print(node.data)
visited.add(node)
for neighbor in node.neighbors:
dfs_recursive(neighbor, visited)#include <iostream>
#include <set>
#include <vector>
void dfs_recursive(Node* node, std::set<Node*>& visited) {
if (!node) return;
if (visited.find(node) == visited.end()) {
std::cout << node->data << std::endl;
visited.insert(node);
for (Node* neighbor : node->neighbors) {
dfs_recursive(neighbor, visited);
}
}
}The Python DFS function uses recursion to visit nodes. It starts with a node, visits it if it hasn't been already, and then recursively visits each of its neighbors. A set is used to keep track of visited nodes to avoid cycles.
Time Complexity: O(V + E) where V is the number of vertices and E the number of edges.
Space Complexity: O(V) to store visited vertices in the worst case.
Approach 2: Iterative Breadth-First Search (BFS)
The BFS iterative approach uses a queue to manage nodes. It explores a neighbor before moving deeper, which helps in finding the shortest path or level-wise processing. This method is beneficial in scenarios where all nodes are needed before moving levels.
import java.util.*;
void bfs_iterative(Node startNode) {
Queue<Node> queue = new LinkedList<>();
Set<Node> visited = new HashSet<>();
queue.add(startNode);
visited.add(startNode);
while (!queue.isEmpty()) {
Node node = queue.poll();
System.out.println(node.data);
for (Node neighbor : node.neighbors) {
if (!visited.contains(neighbor)) {
queue.add(neighbor);
visited.add(neighbor);
}
}
}
}function bfsIterative(startNode) {
let queue = [startNode];
let visited = new Set();
visited.add(startNode);
while (queue.length > 0) {
let node = queue.shift();
console.log(node.data);
for (let neighbor of node.neighbors) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
}This Java BFS method uses a queue to track and visit nodes level by level. It ensures no node is visited more than once by using a set, making it efficient for graph and tree-like data structures.
Time Complexity: O(V + E) where V is the number of vertices and E the number of edges.
Space Complexity: O(V) due to the queue and set for storing visited nodes.
Approach 3: Sorting
The problem essentially asks us to find the length of the longest consecutive increasing subsequence in the array, and then add 1.
We define a function f(nums) to represent the length of the longest consecutive increasing subsequence in the array nums.
For the array nums, we first sort it, then iterate through the array. If the current element nums[i] equals the previous element nums[i - 1] plus 1, it means the current element can be added to the consecutive increasing subsequence. Otherwise, the current element cannot be added to the consecutive increasing subsequence, and we need to restart counting the length of the consecutive increasing subsequence. Finally, we return the length of the consecutive increasing subsequence plus 1.
After finding the lengths of the longest consecutive increasing subsequences in hBars and vBars, we take the minimum of the two as the side length of the square, and then calculate the area of the square.
The time complexity is O(n times log n), and the space complexity is O(n), where n is the length of the array hBars or vBars.
function maximizeSquareHoleArea(n: number, m: number, hBars: number[], vBars: number[]): number {
const f = (nums: number[]): number => {
nums.sort((a, b) => a - b);
let [ans, cnt] = [1, 1];
for (let i = 1; i < nums.length; ++i) {
if (nums[i] === nums[i - 1] + 1) {
ans = Math.max(ans, ++cnt);
} else {
cnt = 1;
}
}
return ans + 1;
};
return Math.min(f(hBars), f(vBars)) ** 2;
}func maximizeSquareHoleArea(n int, m int, hBars []int, vBars []int) int {
f := func(nums []int) int {
sort.Ints(nums)
ans, cnt := 1, 1
for i, x := range nums[1:] {
if x == nums[i]+1 {
cnt++
ans = max(ans, cnt)
} else {
cnt = 1
}
}
return ans + 1
}
x := min(f(hBars), f(vBars))
return x * x
}impl Solution {
pub fn maximize_square_hole_area(n: i32, m: i32, h_bars: Vec<i32>, v_bars: Vec<i32>) -> i32 {
let f = |nums: &mut Vec<i32>| -> i32 {
let mut ans = 1;
let mut cnt = 1;
nums.sort();
for i in 1..nums.len() {
if nums[i] == nums[i - 1] + 1 {
cnt += 1;
ans = ans.max(cnt);
} else {
cnt = 1;
}
}
ans + 1
};
let mut h_bars = h_bars;
let mut v_bars = v_bars;
let x = f(&mut h_bars).min(f(&mut v_bars));
x * x
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Depth-First Search (DFS) | Time Complexity: O(V + E) where V is the number of vertices and E the number of edges. |
| Iterative Breadth-First Search (BFS) | Time Complexity: O(V + E) where V is the number of vertices and E the number of edges. |
| Sorting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive DFS Grid Exploration | O(n*m) | O(n*m) | Conceptual approach when modeling the grid explicitly |
| Iterative BFS Region Expansion | O(n*m) | O(n*m) | When avoiding recursion depth or exploring regions level by level |
| Sorting Consecutive Bars (Optimal) | O(k log k) | O(1) | Best approach when only removed bar indices matter |
Frequently asked questions
Is Maximize Area of Square Hole in Grid easy or hard?
This problem is typically rated Medium. The challenge is recognizing that consecutive removed bars determine the hole size. Once that observation is made, the implementation becomes a straightforward sorting and scanning task.
Maximize Area of Square Hole in Grid Python/Java solution
In Python or Java, store removed bars in arrays, sort them using built-in sorting methods, then iterate once to count consecutive sequences. Compute maxHorizontalGap and maxVerticalGap, take their minimum as the square side, and return side * side.
How to solve Maximize Area of Square Hole in Grid in O(n)?
After sorting the removed bars, the consecutive scan itself is O(n). Iterate through the sorted array and count streaks where adjacent values differ by 1. Track the longest streak and add 1 to get the gap size. Repeat for both horizontal and vertical bars, then compute the square area.
What is the best approach for Maximize Area of Square Hole in Grid?
The most efficient solution sorts the removed horizontal and vertical bars, then scans for the longest consecutive sequence in each list. Removing k consecutive bars creates a gap of size k+1. The largest square side equals the minimum of the largest horizontal and vertical gaps. This approach runs in O(k log k) time due to sorting.
Is Maximize Area of Square Hole in Grid asked at Google/Amazon/Meta?
Problems based on consecutive ranges and grid gaps appear frequently in interviews at companies like Amazon, Google, and Meta. The key skill tested is recognizing patterns after sorting rather than brute-force grid simulation.
What data structure is used in Maximize Area of Square Hole in Grid?
The problem mainly uses arrays combined with sorting. After sorting, a simple linear scan identifies the longest consecutive sequence. No complex data structures like heaps or trees are required.
What is the time complexity of Maximize Area of Square Hole in Grid?
The optimal solution runs in O(k log k) time where k is the number of removed bars. Sorting both arrays dominates the runtime, while the consecutive scan is linear. Space complexity is O(1) if sorting is done in-place.
