Maximize Area of Square Hole in Grid
Source: leetcode
Difficulty: Medium
Tags: array, sorting

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.leetcode.com/uploads/2023/11/05/screenshot-from-2023-11-05-22-40-25.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.leetcode.com/uploads/2023/11/04/screenshot-from-2023-11-04-17-01-02.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.leetcode.com/uploads/2024/03/12/unsaved-image-2.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.




C++ solution:
class Solution {
public:
    int maximizeSquareHoleArea(int n, int m, vector<int>& h, vector<int>& v) {
        int ans, L = 2, R = 2, maxL = 2, maxR = 2;
        sort(h.begin(), h.end());
        sort(v.begin(), v.end());
        for(int i = 0; i < h.size() - 1; i++){
            if(h[i] == h[i + 1] - 1){
                L++;
            }
            else{
                maxL = max(L, maxL);
                L = 2;
            }
        }
        maxL = max(L, maxL);
        for(int i = 0; i < v.size() - 1; i++){
            if(v[i] == v[i + 1] - 1){
                R++;
            }
            else{
                maxR = max(R, maxR);
                R = 2;
            }
        }
        maxR = max(R, maxR);
        return min(maxL, maxR) * min(maxL, maxR);
    }
};

Go solution:
func maximizeSquareHoleArea(n int, m int, hBars []int, vBars []int) int {
  sort.Ints(hBars)
  // We'll identify the max number of consecutive horizontal and vertical bars we can remove
  hcurr, hmax := 1, 1
  for i := 1; i < len(hBars); i++ {
    if hBars[i] == hBars[i-1] + 1 {
      hcurr++
    } else {
      hcurr = 1
    }
    hmax = max(hmax, hcurr)
  }
  sort.Ints(vBars)
  vcurr, vmax := 1, 1
  for j := 1; j < len(vBars); j++ {
    if vBars[j] == vBars[j-1] + 1 {
      vcurr++
    } else {
      vcurr = 1
    }
    vmax = max(vmax, vcurr)
  }
  // Since we need a square shape, we have to remove the same number of
  // horizontal and vertical bars which is the minimum of these two.
  side := min(hmax, vmax)
  return (side+1) * (side+1) // return the area
}

func max(a, b int) int {
  if a > b {
    return a
  }
  return b
}

func min(a, b int) int {
  if a < b {
    return a
  }
  return b
}

Java solution:
public class Solution {
    public int maximizeSquareHoleArea(int n, int m, int[] hBars, int[] vBars) {
        Arrays.sort(hBars);
        Arrays.sort(vBars);
        int mh = 1, mv = 1, c = 1;
        
        for (int i = 1; i < hBars.length; i++) {
            if (hBars[i] == hBars[i - 1] + 1)
                c++;
            else
                c = 1;
            mh = Math.max(mh, c);
        }
        
        c = 1;
        for (int i = 1; i < vBars.length; i++) {
            if (vBars[i] == vBars[i - 1] + 1)
                c++;
            else
                c = 1;
            mv = Math.max(mv, c);
        }
        
        int x = Math.min(mh + 1, mv + 1);
        return x * x;
    }
}

JavaScript solution:
function maximizeSquareHoleArea(n, m, A, B) {
    // Sorting the arrays to identify consecutive elements
    A.sort((a, b) => a - b);
    B.sort((a, b) => a - b);
    
    let mxh = 1, mxv = 1; // Initialization of variables
    
    // Loop through array A to find the maximum horizontal consecutive count
    for (let i = 0; i < A.length; ++i) {
        let cnt = 1; // Counter for consecutive elements
        // Count consecutive elements in A
        while (i + 1 < A.length && A[i] + 1 === A[i + 1]) {
            ++i;
            ++cnt;
        }
        mxh = Math.max(mxh, cnt); // Update maximum horizontal consecutive count
    }
    
    // Loop through array B to find the maximum vertical consecutive count
    for (let i = 0; i < B.length; i++) {
        let cnt = 1; // Counter for consecutive elements
        // Count consecutive elements in B
        while (i + 1 < B.length && B[i] + 1 === B[i + 1]) {
            ++i;
            ++cnt;
        }
        mxv = Math.max(mxv, cnt); // Update maximum vertical consecutive count
    }
    
    // Calculate the maximum possible area for the square hole
    let ans = Math.pow(Math.min(mxh, mxv) + 1, 2);
    return ans; // Return the maximum area of the square-shaped hole
}

Python solution:
class Solution:
    def maximizeSquareHoleArea(
        self, n: int, m: int, hBars: List[int], vBars: List[int]
    ) -> int:
        hBars.sort()
        vBars.sort()

        hcons = {}
        vcons = {}

        i = 0
        while i < len(hBars):
            j = i + 1
            count = 1
            while j < len(hBars):
                if hBars[j] == hBars[j - 1] + 1:
                    count += 1
                else:
                    break
                j += 1
            hcons[hBars[i]] = count
            i = j

        i = 0
        while i < len(vBars):
            j = i + 1
            count = 1
            while j < len(vBars):
                if vBars[j] == vBars[j - 1] + 1:
                    count += 1
                else:
                    break
                j += 1
            vcons[vBars[i]] = count
            i = j

        # print(hcons)
        # print(vcons)

        maxarea = 1
        maxh = max(hcons.values())
        maxv = max(vcons.values())
        maxarea = (min(maxh, maxv) + 1) ** 2
        return maxarea

Ruby solution:
def maximize_square_hole_area(n, m, h, v)
    h.sort!
    v.sort!
    ([max_seq(h), max_seq(v)].min + 1)**2
end

def max_seq(arr)
    return 0 if arr.length == 0
    prev = arr.shift
    max = 1
    curr = 1
    until arr.empty?
        new = arr.shift
        if new == prev + 1
            curr += 1
            max = curr if curr > max
        else
            curr = 1
        end
        prev = new
    end
    max
end