LeetCode Problem 2943

Difficulty: 🟡 Medium
Topics: Array, Sorting

Solution

LeetCode 2943 - Maximize Area of Square Hole in Grid

Problem Understanding

The grid is formed by n + 2 horizontal bars and m + 2 vertical bars. These bars divide the plane into unit squares.

The bars are numbered starting from 1. Some horizontal bars listed in hBars may be removed, and some vertical bars listed in vBars may also be removed. All other bars remain fixed.

Removing a bar merges the adjacent rows or columns separated by that bar. If multiple consecutive bars are removed, an even larger continuous opening is created.

The goal is to create the largest possible square-shaped hole. Since a square requires equal height and width, we need to determine:

• The largest achievable hole height from removable horizontal bars.
• The largest achievable hole width from removable vertical bars.
• The side length of the largest square, which is the minimum of those two values.
• The area, which is the side length squared.

A subtle but important observation is that removing consecutive bars creates larger openings. For example:

• Removing bar 2 creates a gap spanning 2 unit cells.
• Removing bars 2 and 3 creates a gap spanning 3 unit cells.
• Removing bars 2, 3, and 4 creates a gap spanning 4 unit cells.

In general, if we can remove a consecutive sequence of k bars, the resulting opening spans k + 1 cells.

The constraints provide an important hint:

• n and m can be as large as 10^9.
• However, hBars.length and vBars.length are at most 100.

This means we cannot build or simulate the entire grid. The solution must depend only on the removable bar lists, whose sizes are very small.

Important edge cases include:

• Only one removable bar.
• All removable bars are consecutive.
• Multiple disconnected groups of removable bars.
• Horizontal and vertical maximum openings having different sizes.
• Extremely large values of n and m, where only the removable bar lists matter.

Approaches

Brute Force

A brute force solution would try every subset of removable horizontal bars and every subset of removable vertical bars.

For each combination, we would determine the resulting hole dimensions and compute the largest square area.

This approach is correct because it explicitly examines every possible set of removals. However, if there are up to 100 removable bars, the number of subsets becomes astronomical:

• Horizontal choices: 2^100
• Vertical choices: 2^100

The combined search space is completely infeasible.

Key Insight

The exact set of removed bars does not matter. What matters is the longest consecutive sequence of removable bars.

Suppose we have removable bars:

[2,3,4]

We can remove all three bars and create an opening spanning:

3 + 1 = 4 cells

If the longest consecutive removable sequence has length k, then the largest achievable opening is:

k + 1

Therefore:

1. Sort the removable bars.
2. Find the longest consecutive run.
3. Convert that run length into an opening size by adding one.
4. Compute the largest horizontal opening and largest vertical opening.
5. The largest square side length is the smaller of the two openings.
6. Return its area.

Because each list contains at most 100 elements, sorting and scanning are very cheap.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^(h+v))	O(1)	Enumerates every removal combination
Optimal	O(h log h + v log v)	O(1)	Finds longest consecutive removable sequences

Here h = len(hBars) and v = len(vBars).

Algorithm Walkthrough

Step 1

Sort the horizontal removable bars.

Sorting allows consecutive removable bars to appear next to each other, making runs easy to detect.

Step 2

Scan the sorted list and find the longest consecutive sequence.

Maintain:

• currentRun, length of the current consecutive run.
• maxRun, longest run seen so far.

If:

bars[i] == bars[i - 1] + 1

then the run continues.

Otherwise, start a new run of length 1.

Step 3

Convert the longest run into the largest achievable opening.

If the longest consecutive run has length:

maxRun

then the opening spans:

maxRun + 1

cells.

Step 4

Repeat the same process for the vertical bars.

This produces:

horizontalOpening
verticalOpening

Step 5

Compute the maximum square side length.

A square must fit within both dimensions, so:

side = min(horizontalOpening, verticalOpening)

Step 6

Return:

side * side

which is the square area.

Why it works

Removing a bar only increases an opening if it belongs to a consecutive sequence of removable bars. A run of k consecutive removable bars merges k + 1 adjacent cells into one continuous dimension. Therefore the maximum achievable opening in a direction depends solely on the longest consecutive removable run. Computing this independently for horizontal and vertical bars gives the maximum possible height and width. Since a square requires equal dimensions, taking the smaller of the two openings yields the largest valid square side length, and squaring it gives the maximum area.

Python Solution

from typing import List

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

        def max_opening(bars: List[int]) -> int:
            bars.sort()

            longest_run = 1
            current_run = 1

            for i in range(1, len(bars)):
                if bars[i] == bars[i - 1] + 1:
                    current_run += 1
                else:
                    current_run = 1

                longest_run = max(longest_run, current_run)

            return longest_run + 1

        horizontal = max_opening(hBars)
        vertical = max_opening(vBars)

        side = min(horizontal, vertical)
        return side * side

Implementation Explanation

The helper function max_opening computes the largest possible opening in one direction.

The list is first sorted so that consecutive removable bars become adjacent. The scan maintains the current consecutive run length and the maximum run length encountered.

Whenever two neighboring values differ by exactly one, they belong to the same consecutive sequence and the run length increases. Otherwise, the run restarts.

After finding the longest run, we return longest_run + 1, because removing k consecutive bars merges k + 1 cells.

The main function computes the largest horizontal and vertical openings independently. The side length of the largest square is the smaller of those two dimensions. Finally, the area is returned.

Go Solution

package main

import "sort"

func maximizeSquareHoleArea(n int, m int, hBars []int, vBars []int) int {
	maxOpening := func(bars []int) int {
		sort.Ints(bars)

		longestRun := 1
		currentRun := 1

		for i := 1; i < len(bars); i++ {
			if bars[i] == bars[i-1]+1 {
				currentRun++
			} else {
				currentRun = 1
			}

			if currentRun > longestRun {
				longestRun = currentRun
			}
		}

		return longestRun + 1
	}

	horizontal := maxOpening(hBars)
	vertical := maxOpening(vBars)

	side := horizontal
	if vertical < side {
		side = vertical
	}

	return side * side
}

Go-Specific Notes

The Go solution follows exactly the same logic as the Python implementation.

The standard library function sort.Ints is used to sort the slices in place. Since the maximum side length is at most 101, integer overflow is never a concern when computing the area. The solution uses ordinary int values throughout.

Worked Examples

Example 1

n = 2
m = 1
hBars = [2,3]
vBars = [2]

Horizontal Bars

Sorted:

[2,3]

i	Value	Consecutive?	currentRun	longestRun
Start	2	-	1	1
1	3	Yes	2	2

Opening:

2 + 1 = 3

Vertical Bars

Sorted:

[2]

State	currentRun	longestRun
Initial	1	1

Opening:

1 + 1 = 2

Final

side = min(3, 2) = 2
area = 2^2 = 4

Answer:

4

Example 2

n = 1
m = 1
hBars = [2]
vBars = [2]

Horizontal

Longest run:

1

Opening:

2

Vertical

Longest run:

1

Opening:

2

Final

side = 2
area = 4

Answer:

4

Example 3

n = 2
m = 3
hBars = [2,3]
vBars = [2,4]

Horizontal Bars

Sorted:

[2,3]

Longest run:

2

Opening:

3

Vertical Bars

Sorted:

[2,4]

No consecutive bars exist.

Value	currentRun	longestRun
2	1	1
4	1	1

Opening:

2

Final

side = min(3, 2) = 2
area = 4

Answer:

4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(h log h + v log v)	Sorting dominates the runtime
Space	O(1)	Only a few variables are used besides the input arrays

Since hBars.length and vBars.length are at most 100, the sorting cost is extremely small. The subsequent scans are linear in the size of each list.

Test Cases

from typing import List

s = Solution()

assert s.maximizeSquareHoleArea(2, 1, [2, 3], [2]) == 4  # Example 1
assert s.maximizeSquareHoleArea(1, 1, [2], [2]) == 4  # Example 2
assert s.maximizeSquareHoleArea(2, 3, [2, 3], [2, 4]) == 4  # Example 3

assert s.maximizeSquareHoleArea(5, 5, [2], [2]) == 4  # Single removable bar each
assert s.maximizeSquareHoleArea(5, 5, [2, 3, 4], [2, 3, 4]) == 16  # Long consecutive runs
assert s.maximizeSquareHoleArea(10, 10, [2, 4, 6], [2, 4, 6]) == 4  # No consecutive bars
assert s.maximizeSquareHoleArea(10, 10, [2, 3, 4, 8, 9], [2, 3]) == 9  # Multiple groups
assert s.maximizeSquareHoleArea(10, 10, [5, 6, 7, 8], [2]) == 4  # Width limits square
assert s.maximizeSquareHoleArea(10**9, 10**9, [2, 3], [2, 3, 4]) == 9  # Large n and m
assert s.maximizeSquareHoleArea(20, 20, [2, 3, 5, 6, 7], [4, 5, 6]) == 16  # Different run sizes

Test Summary

Test	Why
(2,1,[2,3],[2])	Official example 1
(1,1,[2],[2])	Official example 2
(2,3,[2,3],[2,4])	Official example 3
Single removable bar	Smallest meaningful run
Long consecutive runs	Largest opening created by one block
No consecutive bars	Every run length remains 1
Multiple groups	Must choose longest run
Large horizontal run, small vertical run	Square limited by smaller dimension
Very large n,m	Confirms independence from grid size
Different run lengths	Validates min(height, width) logic

Edge Cases

Only One Removable Bar

When a list contains exactly one removable bar, the longest consecutive run length is 1. A common mistake is to return 1 as the opening size. In reality, removing one bar merges two adjacent cells, creating an opening of size 2. The implementation correctly returns longest_run + 1, producing an opening size of 2.

Multiple Disconnected Consecutive Groups

Consider:

[2,3,7,8,9]

There are two groups:

[2,3]
[7,8,9]

The algorithm does not stop after finding the first group. It scans the entire sorted list and continuously updates longest_run, ensuring the largest group is selected.

No Consecutive Removable Bars

Consider:

[2,4,6,8]

Every removable bar is isolated. Each run length remains 1, which means the largest opening is:

1 + 1 = 2

The implementation correctly resets current_run whenever a gap larger than one appears and therefore handles isolated bars without special cases.

Extremely Large Grid Dimensions

The values of n and m may reach 10^9, making any grid simulation impossible. The solution never constructs the grid or iterates across its dimensions. It relies entirely on the removable bar lists, whose lengths are at most 100, keeping the algorithm efficient regardless of how large the grid dimensions become.