HardNo. 0302LeetCode Premium
Smallest Rectangle Enclosing Black Pixels — LeetCode 302 Python Solution
- Pattern
- Matrix and Grid
- Topics
- Depth-First Search, Breadth-First Search, Array, Binary Search, Matrix
- Reading time
- 8 min
- Source
- leetcode.com
The problem
You are given an m x n binary matrix image where 0 represents a white pixel and 1 represents a black pixel. The black pixels are connected (i.e., there is only one black region).
Example
- Input
- image = [["0","0","1","0"],["0","1","1","0"],["0","1","0","0"]], x = 0, y = 2
- Output
- 6
Python solution
class Solution:
def minArea(self, image: List[List[str]], x: int, y: int) -> int:
m, n = len(image), len(image[0])
left, right = 0, x
while left < right:
mid = (left + right) >> 1
c = 0
while c < n and image[mid][c] == '0':
c += 1
if c < n:
right = mid
else:
left = mid + 1
u = left
left, right = x, m - 1
while left < right:
mid = (left + right + 1) >> 1
c = 0
while c < n and image[mid][c] == '0':
c += 1
if c < n:
left = mid
else:
right = mid - 1
d = left
left, right = 0, y
while left < right:
mid = (left + right) >> 1
r = 0
while r < m and image[r][mid] == '0':
r += 1
if r < m:
right = mid
else:
left = mid + 1
l = left
left, right = y, n - 1
while left < right:
mid = (left + right + 1) >> 1
r = 0
while r < m and image[r][mid] == '0':
r += 1
if r < m:
left = mid
else:
right = mid - 1
r = left
return (d - u + 1) * (r - l + 1)Complexity
- Time
- O(log n) or O(n log n)
- Space · auxiliary
- O(1)
Pattern: Matrix and Grid
Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 302. Smallest Rectangle Enclosing Black Pixels is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.
The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0778 | Swim in Rising Water | Hard |
| 1631 | Path With Minimum Effort | Medium |
| 1970 | Last Day Where You Can Still Cross | Hard |
| 2258 | Escape the Spreading Fire | Hard |
| 2812 | Find the Safest Path in a Grid | Medium |
| 0074 | Search a 2D Matrix | Medium |
Frequently asked questions
- How hard is LeetCode 302. Smallest Rectangle Enclosing Black Pixels?
LeetCode 302. Smallest Rectangle Enclosing Black Pixels is rated Hard on LeetCode.
- What topics does LeetCode 302. Smallest Rectangle Enclosing Black Pixels cover?
LeetCode 302. Smallest Rectangle Enclosing Black Pixels is tagged Depth-First Search, Breadth-First Search, Array, Binary Search and Matrix on LeetCode.
- Is LeetCode 302. Smallest Rectangle Enclosing Black Pixels a premium problem?
Yes. LeetCode 302. Smallest Rectangle Enclosing Black Pixels is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.