This write-up documents how I solved the LeetCode problem that asks for the largest square hole that can be carved out of a grid after removing a subset of horizontal and vertical bars. The key is to sort the removed bars and measure the longest consecutive runs along each axis.
Once we have those runs, the answer is simply the square of one plus the minimum run length because the hole must have the same side length in both dimensions.
Decision points
- Sort the removed horizontal bars and determine the widest gap to understand how tall the hole can be.
- Do the same for vertical bars to find the widest possible width.
- The square side length is the minimum of those two maxima plus one (accounting for grid boundaries).
Complexity
Sorting dominates the runtime at O(n log n), where n is the number of removed bars. We only traverse the sorted arrays twice afterwards.
Source
You can view the accompanying solution file or the original problem statement for finer details:
- LeetCode problem page
- Repository path:
maximize-area-of-square-hole-in-grid/solution.ts