# Maximize Area of Square Hole in Grid
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximize-area-of-square-hole-in-grid)
Canonical: https://scaleengineer.com/dsa/problems/maximize-area-of-square-hole-in-grid
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Swiggy](https://scaleengineer.com/companies/swiggy)
---
## 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:**

![](https://assets.glich.co/dsa/maximize-area-of-square-hole-in-grid/image0.png)

**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:**

![](https://assets.glich.co/dsa/maximize-area-of-square-hole-in-grid/image1.png)

**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:**

![](https://assets.glich.co/dsa/maximize-area-of-square-hole-in-grid/image2.png)

**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 <= 109`
* `1 <= m <= 109`
* `1 <= hBars.length <= 100`
* `2 <= hBars[i] <= n + 1`
* `1 <= vBars.length <= 100`
* `2 <= vBars[i] <= m + 1`
* All values in `hBars` are distinct.
* All values in `vBars` are distinct.

# Approaches
## Brute-Force Check for Consecutive Sequences
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.
**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.
**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.
### Explanation
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.

```java
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
    }
}
```
### Algorithm
*   Iterate `s` from `min(hBars.length, vBars.length) + 1` down to 1.
*   For each `s`, let `k = s - 1`.
*   Define a helper function `hasConsecutive(bars, k)`:
    *   For each `startBar` in `bars`:
        *   Assume a sequence is found.
        *   For `i` from 1 to `k-1`, check if `startBar + i` exists in `bars` by iterating through `bars` again.
        *   If any element is not found, this is not a valid sequence from `startBar`.
        *   If all `k-1` elements are found, return `true`.
    *   If the loop finishes, return `false`.
*   Call `hasConsecutive` for `hBars` and `vBars` with `k`.
*   If both calls return `true`, we have found the maximum side `s`. Return `s * s`.
*   If the loop finishes, it means the maximum side is 1. Return 1.

## Linear Scan on Answer with Hash Set Optimization
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.
**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)).
**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.
### Explanation
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:
1.  First, we insert all elements of the `bars` array into a `HashSet`. This takes `O(L)` time, where `L` is the length of the array.
2.  Then, to check if a sequence of at least length `k` exists, we iterate through each unique bar `b` in the hash set.
3.  For each `b`, we check if it's the start of a sequence by verifying that `b-1` is *not* in the set. This avoids redundant checks.
4.  If `b` is a starting point, we count how long the consecutive sequence is by repeatedly checking for `b+1, b+2, ...` in the hash set.
5.  If the length of any found sequence is greater than or equal to `k`, we can immediately return `true`.
6.  If we check all possible starting points and none yield a sequence of length `k`, we return `false`.

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.

```java
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
    }
}
```
### Algorithm
*   Iterate `s` from `min(hBars.length, vBars.length) + 1` down to 1.
*   For each `s`, let `k = s - 1`.
*   Define an optimized helper function `hasConsecutive(bars, k)`:
    *   Create a `HashSet` and add all elements from `bars` to it.
    *   For each `bar` in the set:
        *   If `bar - 1` is not in the set, this `bar` is the start of a potential sequence.
        *   Count the length of the consecutive sequence starting from `bar`.
        *   If this length is `>= k`, return `true`.
    *   If the loop finishes, return `false`.
*   Call this optimized `hasConsecutive` for `hBars` and `vBars` with `k`.
*   If both calls return `true`, return `s * s`.
*   If the loop finishes, return 1.

## Finding Maximum Consecutive Gaps by Sorting
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.
**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.
**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.
### Explanation
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_consecutive` be the length of the longest run of consecutive integers in `hBars`. By removing these bars, we can create a hole with a maximum height of `max_h_consecutive + 1`.
*   Similarly, let `max_v_consecutive` be the length of the longest run of consecutive integers in `vBars`. This allows for a maximum width of `max_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.

```java
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);
    }
}
```
### 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 `bars` array.
    *   Initialize `maxLength = 1` and `currentLength = 1`.
    *   Iterate through the sorted array from the second element (`i=1`).
    *   If `bars[i] == bars[i-1] + 1`, the numbers are consecutive, so increment `currentLength`.
    *   If they are not consecutive (i.e., `bars[i] > bars[i-1] + 1`), the sequence is broken, so reset `currentLength` to 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`.

# Solutions
### Java

```java
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;
  }
}

```

### Python

```python
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)) ** 2

```

### CPP

```cpp
class 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;
  }
};

```