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 + 1hBars are distinct.vBars are distinct.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.
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.
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.
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.
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.
Java
JavaScript
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.
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.
| 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 | — |
| 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 |
Maximize Area of Square Hole in Grid | Detailed Intuition | Leetcode 2943 | codestorywithMIK • codestorywithMIK • 9,130 views views
Watch 9 more video solutions →Practice Maximize Area of Square Hole in Grid with our built-in code editor and test cases.
Practice on FleetCode