MediumNo. 2943
Maximize Area of Square Hole in Grid — LeetCode 2943 Python Solution
- Pattern
- Sorting
- Topics
- Array, Sorting
- Reading time
- 3 min
- Source
- leetcode.com
The 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.
Python solution
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)) ** 2Complexity
- Time
- O(n × log n)
- Space · auxiliary
- O(n)where n is the length of the array hBars or vBars
Pattern: Sorting
Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 2943. Maximize Area of Square Hole in Grid is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.
The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0056 | Merge Intervals | Medium |
| 0164 | Maximum Gap | Medium |
| 0274 | H-Index | Medium |
| 0406 | Queue Reconstruction by Height | Medium |
| 0414 | Third Maximum Number | Easy |
| 0462 | Minimum Moves to Equal Array Elements II | Medium |
Frequently asked questions
- How hard is LeetCode 2943. Maximize Area of Square Hole in Grid?
LeetCode 2943. Maximize Area of Square Hole in Grid is rated Medium on LeetCode.
- What topics does LeetCode 2943. Maximize Area of Square Hole in Grid cover?
LeetCode 2943. Maximize Area of Square Hole in Grid is tagged Array and Sorting on LeetCode.