LeetCode 302: Smallest Rectangle Enclosing Black Pixels

Problem Restatement

We are given an m x n binary matrix image.

Each cell is either:

All black pixels form one connected component. Pixels are connected horizontally and vertically.

We are also given coordinates (x, y) of one black pixel.

Return the area of the smallest axis-aligned rectangle that encloses all black pixels.

The required algorithm must run in less than O(mn) time. The official constraints include image[x][y] == "1" and one connected black component.

Input and Output

Function shape:

def minArea(image: list[list[str]], x: int, y: int) -> int:
    ...

Examples

Example 1:

image = [
    ["0", "0", "1", "0"],
    ["0", "1", "1", "0"],
    ["0", "1", "0", "0"],
]
x = 0
y = 2

The black pixels are at:

(0, 2), (1, 1), (1, 2), (2, 1)

The smallest rectangle containing them spans:

Height:

2 - 0 + 1 = 3

Width:

2 - 1 + 1 = 2

Area:

3 * 2 = 6

Output:

6

Example 2:

image = [["1"]]
x = 0
y = 0

There is only one black pixel.

The smallest rectangle has area:

1

First Thought: Full Matrix Scan

The simplest solution scans every cell.

Whenever we find a black pixel, update four boundaries:

top = min(top, row)
bottom = max(bottom, row)
left = min(left, col)
right = max(right, col)

Then compute:

(bottom - top + 1) * (right - left + 1)

This is easy and correct.

But it scans all m * n cells, so the time complexity is:

O(mn)

The problem asks for less than O(mn), so we need a faster method.

Key Insight

The rectangle is determined by four boundaries:

Since the black pixels form one connected region, the set of rows containing at least one black pixel is continuous.

For example, if rows 1 and 4 contain black pixels, then rows 2 and 3 must also contain black pixels somewhere. Otherwise, the black component would be disconnected vertically.

The same idea applies to columns.

That gives us a binary-searchable structure.

For rows:

no black, no black, black, black, black, no black

For columns:

no black, black, black, black, no black

So we can binary search for:

1. First row with black pixel.
2. First row after the black region.
3. First column with black pixel.
4. First column after the black region.

Row and Column Checks

We need two helper checks.

To check whether a row contains a black pixel:

def row_has_black(row: int) -> bool:
    return any(image[row][col] == "1" for col in range(n))

To check whether a column contains a black pixel:

def col_has_black(col: int) -> bool:
    return any(image[row][col] == "1" for row in range(m))

A row check costs O(n).

A column check costs O(m).

Binary search keeps the number of checks small.

Binary Search Boundary Function

We use one helper function:

def search(lo: int, hi: int, check, target: bool) -> int:
    while lo < hi:
        mid = (lo + hi) // 2

        if check(mid) == target:
            hi = mid
        else:
            lo = mid + 1

    return lo

This returns the first index in [lo, hi) where:

check(index) == target

We can use it for both left-side and right-side boundaries.

Algorithm

Let:

m = len(image)
n = len(image[0])

Find the four boundaries:

top = search(0, x + 1, row_has_black, True)
bottom = search(x + 1, m, row_has_black, False)

left = search(0, y + 1, col_has_black, True)
right = search(y + 1, n, col_has_black, False)

Important detail:

bottom is the first row after the black region.

right is the first column after the black region.

So the height is:

bottom - top

The width is:

right - left

Return:

(bottom - top) * (right - left)

Correctness

The smallest rectangle enclosing all black pixels must start at the first row that contains a black pixel and end after the last row that contains a black pixel.

It must also start at the first column that contains a black pixel and end after the last column that contains a black pixel.

Because all black pixels are connected, rows containing black pixels form one continuous interval. Therefore, among rows from 0 to x, there is a transition from rows without black pixels to rows with black pixels. Binary search finds the first row in that interval that contains a black pixel. This is exactly top.

Among rows from x + 1 to m, there is a transition from rows with black pixels to rows without black pixels. Binary search finds the first row after x that does not contain a black pixel. This is exactly one row after the bottom boundary.

The same reasoning applies to columns. Binary search over columns finds the left boundary and one column after the right boundary.

So the algorithm computes the exact height and width of the smallest enclosing rectangle. Multiplying them gives the required area.

Complexity

This is less than O(mn) for large matrices.

Implementation

class Solution:
    def minArea(self, image: list[list[str]], x: int, y: int) -> int:
        m = len(image)
        n = len(image[0])

        def row_has_black(row: int) -> bool:
            return any(image[row][col] == "1" for col in range(n))

        def col_has_black(col: int) -> bool:
            return any(image[row][col] == "1" for row in range(m))

        def search(lo: int, hi: int, check, target: bool) -> int:
            while lo < hi:
                mid = (lo + hi) // 2

                if check(mid) == target:
                    hi = mid
                else:
                    lo = mid + 1

            return lo

        top = search(0, x + 1, row_has_black, True)
        bottom = search(x + 1, m, row_has_black, False)

        left = search(0, y + 1, col_has_black, True)
        right = search(y + 1, n, col_has_black, False)

        return (bottom - top) * (right - left)

Code Explanation

We first store the matrix size.

m = len(image)
n = len(image[0])

The row check asks whether a row contains at least one black pixel.

def row_has_black(row: int) -> bool:
    return any(image[row][col] == "1" for col in range(n))

The column check asks whether a column contains at least one black pixel.

def col_has_black(col: int) -> bool:
    return any(image[row][col] == "1" for row in range(m))

The search helper finds the first index in a half-open interval [lo, hi) where check(index) equals target.

def search(lo: int, hi: int, check, target: bool) -> int:

When the middle index has the desired property, the answer may be at mid or before it.

if check(mid) == target:
    hi = mid

Otherwise, the answer must be after mid.

else:
    lo = mid + 1

Now we find the four boundaries.

top = search(0, x + 1, row_has_black, True)

This finds the first row with a black pixel between the top of the matrix and row x.

bottom = search(x + 1, m, row_has_black, False)

This finds the first row after x with no black pixel. That is one row after the bottom boundary.

left = search(0, y + 1, col_has_black, True)

This finds the first column with a black pixel between the left side and column y.

right = search(y + 1, n, col_has_black, False)

This finds the first column after y with no black pixel. That is one column after the right boundary.

Finally:

return (bottom - top) * (right - left)

Because bottom and right are exclusive boundaries, no + 1 is needed.

Testing

def run_tests():
    s = Solution()

    image1 = [
        ["0", "0", "1", "0"],
        ["0", "1", "1", "0"],
        ["0", "1", "0", "0"],
    ]
    assert s.minArea(image1, 0, 2) == 6

    image2 = [["1"]]
    assert s.minArea(image2, 0, 0) == 1

    image3 = [
        ["0", "1", "0"],
        ["0", "1", "0"],
        ["0", "1", "0"],
    ]
    assert s.minArea(image3, 1, 1) == 3

    image4 = [
        ["0", "0", "0"],
        ["1", "1", "1"],
        ["0", "0", "0"],
    ]
    assert s.minArea(image4, 1, 1) == 3

    image5 = [
        ["1", "1"],
        ["1", "1"],
    ]
    assert s.minArea(image5, 0, 0) == 4

    print("all tests passed")

run_tests()

Test meaning: