Find the largest square hole that can be formed in a grid after removing selected horizontal and vertical bars.
You are given an grid formed by horizontal and vertical bars. Some of the bars are removed from the grid.
A square hole appears when a consecutive block of removed horizontal bars and a consecutive block of removed vertical bars create a larger open square region.
Your task is to determine the maximum possible area of a square hole that can be formed after the removals.
In other words, find the side length of the largest square that can fit inside the opened space, then return its area.
Input Format
A typical instance contains:
- Two integers describing the grid dimensions.
- Two arrays/lists describing which horizontal bars are removed and which vertical bars are removed.
Output Format
Return a single integer: the maximum area of a square hole that can be formed.
Constraints
The removed bar indices are positive integers and refer to bars in the grid. The solution should run efficiently for large input sizes, typically near linearithmic or linear time after preprocessing.
Example 1
Input
n = 6, m = 6 horizontalBars = [2, 3, 4] verticalBars = [2, 3]
Output
9
Explanation
The longest consecutive removed horizontal run has length 3, and the longest consecutive removed vertical run has length 2. The largest square side length is min(3, 2) + 1 = 3, so the area is = 9.
Example 2
Input
n = 5, m = 5 horizontalBars = [1] verticalBars = [4]
Output
4
Explanation
There is only one removed bar in each direction, so the largest square side length is 2 and the area is = 4.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.