LeetCode 302 - Smallest Rectangle Enclosing Black Pixels
This problem gives us a binary matrix where each cell contains either '0' or '1'. A '1' represents a black pixel, while a '0' represents a white pixel.
Difficulty: 🔴 Hard
Topics: Array, Binary Search, Depth-First Search, Breadth-First Search, Matrix
Solution
Problem Understanding
This problem gives us a binary matrix where each cell contains either '0' or '1'. A '1' represents a black pixel, while a '0' represents a white pixel. All black pixels belong to exactly one connected component, meaning every black pixel can be reached from every other black pixel using only horizontal or vertical movement.
We are also given the coordinates (x, y) of one black pixel. Our task is to compute the area of the smallest axis-aligned rectangle that contains every black pixel in the image.
An axis-aligned rectangle means the rectangle sides must remain parallel to the matrix rows and columns. Therefore, we only need to determine four boundaries:
- The topmost row containing a black pixel
- The bottommost row containing a black pixel
- The leftmost column containing a black pixel
- The rightmost column containing a black pixel
Once these boundaries are known, the rectangle area is:
$$(\text{bottom} - \text{top} + 1) \times (\text{right} - \text{left} + 1)$$
The important constraint is that the algorithm must run in less than O(mn) time, where m is the number of rows and n is the number of columns. A straightforward full scan of the matrix visits every cell, which costs O(mn), so we need something more efficient.
The key observation is that all black pixels form one connected component. This means the rows containing black pixels form a continuous interval, and the columns containing black pixels also form a continuous interval. That monotonic structure allows us to use binary search to locate the rectangle boundaries efficiently.
Several edge cases are important:
- The image may contain only one black pixel.
- The black region may span the entire matrix.
- The black component may occupy a single row or a single column.
- The provided
(x, y)may already lie on one of the rectangle boundaries. - The matrix dimensions may be as small as
1 x 1.
The problem guarantees that:
(x, y)is always a black pixel.- There is exactly one connected black region.
- The matrix dimensions are at most
100 x 100.
These guarantees simplify the solution considerably.
Approaches
Brute Force Approach
The simplest solution is to scan every cell in the matrix. Whenever we encounter a black pixel, we update four variables:
- Minimum row index
- Maximum row index
- Minimum column index
- Maximum column index
At the end, we compute the rectangle area from these boundaries.
This approach is correct because it directly examines every black pixel and records the extreme coordinates. However, it always visits all m * n cells, even if the black region is tiny.
Since the problem explicitly requires better than O(mn) complexity, this approach is not sufficient.
Optimal Approach, Binary Search on Rows and Columns
The important insight is that black pixels form one connected region. Because of this:
- All rows containing black pixels appear consecutively.
- All columns containing black pixels appear consecutively.
Suppose we define a helper function:
rowHasBlack(row)returns whether a row contains at least one black pixel.colHasBlack(col)returns whether a column contains at least one black pixel.
Then the rows look like this conceptually:
False False False True True True False False
The same property holds for columns.
This monotonic pattern allows binary search to locate:
- The first row containing black pixels
- The first row after the black region
- The first column containing black pixels
- The first column after the black region
Each binary search checks either an entire row or an entire column.
This reduces the runtime to:
$$O(m \log n + n \log m)$$
which is strictly better than O(mn).
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(mn) | O(1) | Scan every cell and track boundaries |
| Optimal | O(m log n + n log m) | O(1) | Binary search rows and columns using monotonic structure |
Algorithm Walkthrough
Step 1: Determine Matrix Dimensions
First, store the number of rows and columns:
rows = len(image)
cols = len(image[0])
We need these dimensions repeatedly during binary searches.
Step 2: Create a Helper Function for Rows
We define a function that checks whether a row contains at least one black pixel.
def row_has_black(row):
return '1' in image[row]
This function scans one row in O(n) time.
The result behaves monotonically:
- Rows before the black region return
False - Rows inside the region return
True - Rows after the region return
False
Step 3: Create a Helper Function for Columns
We also define a function for columns:
def col_has_black(col):
for row in range(rows):
if image[row][col] == '1':
return True
return False
This scans one column in O(m) time.
Again, the results form a monotonic structure.
Step 4: Binary Search for the Top Boundary
We search rows from 0 to x.
We want the first row containing a black pixel.
If the middle row contains black pixels, the top boundary could still be above it, so we move left.
Otherwise, we move right.
Step 5: Binary Search for the Bottom Boundary
We search rows from x + 1 to rows.
This time we look for the first row that does not contain black pixels.
The actual bottom boundary is one row before that position.
Step 6: Binary Search for the Left Boundary
We search columns from 0 to y.
We want the first column containing black pixels.
Step 7: Binary Search for the Right Boundary
We search columns from y + 1 to cols.
We look for the first column without black pixels.
The actual right boundary is one column before that position.
Step 8: Compute the Rectangle Area
Once all boundaries are known:
height = bottom - top
width = right - left
The area becomes:
height * width
Why it works
The algorithm relies on the fact that all black pixels belong to one connected component. Because of this, rows containing black pixels must form one continuous interval. The same is true for columns.
Binary search works whenever a search space can be divided into two monotonic regions. Here, rows transition from:
no black pixels -> black pixels -> no black pixels
The same property holds for columns. Therefore, binary search correctly identifies the rectangle boundaries.
Python Solution
from typing import List
class Solution:
def minArea(self, image: List[List[str]], x: int, y: int) -> int:
rows = len(image)
cols = len(image[0])
def row_has_black(row: int) -> bool:
return '1' in image[row]
def col_has_black(col: int) -> bool:
for row in range(rows):
if image[row][col] == '1':
return True
return False
# Find top boundary
left = 0
right = x
while left < right:
mid = (left + right) // 2
if row_has_black(mid):
right = mid
else:
left = mid + 1
top = left
# Find bottom boundary
left = x + 1
right = rows
while left < right:
mid = (left + right) // 2
if row_has_black(mid):
left = mid + 1
else:
right = mid
bottom = left
# Find left boundary
left = 0
right = y
while left < right:
mid = (left + right) // 2
if col_has_black(mid):
right = mid
else:
left = mid + 1
left_boundary = left
# Find right boundary
left = y + 1
right = cols
while left < right:
mid = (left + right) // 2
if col_has_black(mid):
left = mid + 1
else:
right = mid
right_boundary = left
return (bottom - top) * (right_boundary - left_boundary)
The implementation begins by storing the matrix dimensions. Two helper functions are then defined. One checks whether a row contains any black pixels, and the other checks whether a column contains any black pixels.
The first binary search finds the topmost row containing black pixels. Since the given coordinate (x, y) is guaranteed to be black, we know the top boundary lies somewhere between row 0 and row x.
The second binary search finds the first row after the black region. This gives us the exclusive lower boundary.
The same strategy is repeated for columns.
Finally, the rectangle dimensions are computed using exclusive boundaries:
height = bottom - top
width = right_boundary - left_boundary
Multiplying them gives the final area.
Go Solution
func minArea(image [][]byte, x int, y int) int {
rows := len(image)
cols := len(image[0])
rowHasBlack := func(row int) bool {
for col := 0; col < cols; col++ {
if image[row][col] == '1' {
return true
}
}
return false
}
colHasBlack := func(col int) bool {
for row := 0; row < rows; row++ {
if image[row][col] == '1' {
return true
}
}
return false
}
// Find top boundary
left, right := 0, x
for left < right {
mid := (left + right) / 2
if rowHasBlack(mid) {
right = mid
} else {
left = mid + 1
}
}
top := left
// Find bottom boundary
left, right = x+1, rows
for left < right {
mid := (left + right) / 2
if rowHasBlack(mid) {
left = mid + 1
} else {
right = mid
}
}
bottom := left
// Find left boundary
left, right = 0, y
for left < right {
mid := (left + right) / 2
if colHasBlack(mid) {
right = mid
} else {
left = mid + 1
}
}
leftBoundary := left
// Find right boundary
left, right = y+1, cols
for left < right {
mid := (left + right) / 2
if colHasBlack(mid) {
left = mid + 1
} else {
right = mid
}
}
rightBoundary := left
return (bottom - top) * (rightBoundary - leftBoundary)
}
The Go implementation follows the same logic as the Python solution. The primary difference is that Go uses [][]byte instead of List[List[str]].
Helper functions are implemented as closures. Since Go does not support Python's convenient '1' in row syntax, each row must be scanned manually.
No special handling for integer overflow is necessary because the matrix dimensions are at most 100 x 100, so the maximum possible area is only 10,000.
Worked Examples
Example 1
Input:
image =
[
["0","0","1","0"],
["0","1","1","0"],
["0","1","0","0"]
]
x = 0
y = 2
The black pixels are located at:
(0,2), (1,1), (1,2), (2,1)
Find Top Boundary
Search rows [0, 0]
| left | right | mid | row_has_black(mid) | Action |
|---|---|---|---|---|
| 0 | 0 | - | - | Stop |
Result:
top = 0
Find Bottom Boundary
Search rows [1, 3)
| left | right | mid | row_has_black(mid) | Action |
|---|---|---|---|---|
| 1 | 3 | 2 | True | left = 3 |
Result:
bottom = 3
Find Left Boundary
Search columns [0, 2]
| left | right | mid | col_has_black(mid) | Action |
|---|---|---|---|---|
| 0 | 2 | 1 | True | right = 1 |
| 0 | 1 | 0 | False | left = 1 |
Result:
left_boundary = 1
Find Right Boundary
Search columns [3, 4)
| left | right | mid | col_has_black(mid) | Action |
|---|---|---|---|---|
| 3 | 4 | 3 | False | right = 3 |
Result:
right_boundary = 3
Final Area
height = 3 - 0 = 3
width = 3 - 1 = 2
area = 3 * 2 = 6
Example 2
Input:
image = [["1"]]
x = 0
y = 0
The only pixel is black.
Boundaries become:
top = 0
bottom = 1
left_boundary = 0
right_boundary = 1
Area:
(1 - 0) * (1 - 0) = 1
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(m log n + n log m) | Each binary search checks rows or columns repeatedly |
| Space | O(1) | Only a few variables are used |
Each row check scans n columns, and binary search performs O(log m) row searches. Therefore, row searching costs O(n log m).
Similarly, each column check scans m rows, and binary search performs O(log n) column searches. Therefore, column searching costs O(m log n).
Adding them together gives:
$$O(m \log n + n \log m)$$
The algorithm uses constant extra memory because it only stores a few indices and helper functions.
Test Cases
from typing import List
class Solution:
def minArea(self, image: List[List[str]], x: int, y: int) -> int:
rows = len(image)
cols = len(image[0])
def row_has_black(row: int) -> bool:
return '1' in image[row]
def col_has_black(col: int) -> bool:
for row in range(rows):
if image[row][col] == '1':
return True
return False
left = 0
right = x
while left < right:
mid = (left + right) // 2
if row_has_black(mid):
right = mid
else:
left = mid + 1
top = left
left = x + 1
right = rows
while left < right:
mid = (left + right) // 2
if row_has_black(mid):
left = mid + 1
else:
right = mid
bottom = left
left = 0
right = y
while left < right:
mid = (left + right) // 2
if col_has_black(mid):
right = mid
else:
left = mid + 1
left_boundary = left
left = y + 1
right = cols
while left < right:
mid = (left + right) // 2
if col_has_black(mid):
left = mid + 1
else:
right = mid
right_boundary = left
return (bottom - top) * (right_boundary - left_boundary)
solution = Solution()
# Example 1
assert solution.minArea(
[["0","0","1","0"],
["0","1","1","0"],
["0","1","0","0"]],
0,
2
) == 6 # standard connected region
# Example 2
assert solution.minArea([["1"]], 0, 0) == 1 # single black pixel
# Single row
assert solution.minArea(
[["0","1","1","1","0"]],
0,
2
) == 3 # rectangle in one row
# Single column
assert solution.minArea(
[["0"],
["1"],
["1"],
["0"]],
1,
0
) == 2 # rectangle in one column
# Entire matrix black
assert solution.minArea(
[["1","1"],
["1","1"]],
0,
0
) == 4 # full matrix rectangle
# Black region touching borders
assert solution.minArea(
[["1","0","0"],
["1","1","0"],
["0","1","0"]],
0,
0
) == 4 # touches top and left borders
# Thin vertical rectangle
assert solution.minArea(
[["0","1","0"],
["0","1","0"],
["0","1","0"]],
1,
1
) == 3 # width is 1
# Thin horizontal rectangle
assert solution.minArea(
[["0","0","0"],
["1","1","1"],
["0","0","0"]],
1,
1
) == 3 # height is 1
| Test | Why |
|---|---|
| Standard connected region | Validates general correctness |
| Single black pixel | Smallest possible input |
| Single row region | Ensures horizontal rectangles work |
| Single column region | Ensures vertical rectangles work |
| Entire matrix black | Tests maximum rectangle coverage |
| Region touching borders | Verifies boundary handling |
| Thin vertical rectangle | Tests width equal to 1 |
| Thin horizontal rectangle | Tests height equal to 1 |
Edge Cases
Single Black Pixel
The smallest possible input is a matrix containing exactly one black pixel. This case can expose off-by-one errors when computing rectangle dimensions.
For example:
[["1"]]
The implementation handles this correctly because the binary searches return exclusive boundaries:
top = 0
bottom = 1
left = 0
right = 1
The resulting area becomes 1.
Black Region Occupies Entire Matrix
If every cell is black, the rectangle should cover the entire matrix.
A buggy implementation might incorrectly stop binary search early or fail to include the last row or column.
The algorithm handles this correctly because:
- The bottom boundary search looks for the first row without black pixels.
- The right boundary search looks for the first column without black pixels.
When no such row or column exists, the searches naturally terminate at rows and cols.
Rectangle Width or Height Equals One
A connected black region may form a thin line.
Examples:
Vertical:
0 1 0
0 1 0
0 1 0
Horizontal:
1 1 1
These cases are common sources of off-by-one mistakes because one dimension equals 1.
The implementation uses exclusive boundaries consistently:
height = bottom - top
width = right - left
This ensures rectangles with width 1 or height 1 are computed correctly.