# LeetCode 302: Smallest Rectangle Enclosing Black Pixels

## Problem Restatement

We are given an `m x n` binary matrix `image`.

Each cell is either:

| Value | Meaning |
|---|---|
| `"0"` | White pixel |
| `"1"` | Black pixel |

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

| Item | Meaning |
|---|---|
| Input | A binary matrix `image`, and integers `x`, `y` |
| Output | Area of the smallest rectangle enclosing all black pixels |
| Given | `image[x][y] == "1"` |
| Condition | All black pixels are connected horizontally and vertically |
| Target | Better than `O(mn)` runtime |

Function shape:

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

## Examples

Example 1:

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

The black pixels are at:

```text
(0, 2), (1, 1), (1, 2), (2, 1)
```

The smallest rectangle containing them spans:

| Boundary | Value |
|---|---|
| Top row | `0` |
| Bottom row | `2` |
| Left column | `1` |
| Right column | `2` |

Height:

```python
2 - 0 + 1 = 3
```

Width:

```python
2 - 1 + 1 = 2
```

Area:

```python
3 * 2 = 6
```

Output:

```python
6
```

Example 2:

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

There is only one black pixel.

The smallest rectangle has area:

```python
1
```

## First Thought: Full Matrix Scan

The simplest solution scans every cell.

Whenever we find a black pixel, update four boundaries:

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

Then compute:

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

This is easy and correct.

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

```python
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:

| Boundary | Meaning |
|---|---|
| `top` | First row containing a black pixel |
| `bottom` | Last row containing a black pixel |
| `left` | First column containing a black pixel |
| `right` | Last column containing a black pixel |

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:

```text
no black, no black, black, black, black, no black
```

For columns:

```text
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:

```python
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:

```python
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:

```python
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:

```python
check(index) == target
```

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

## Algorithm

Let:

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

Find the four boundaries:

```python
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:

```python
bottom - top
```

The width is:

```python
right - left
```

Return:

```python
(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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n log m + m log n)` | Row searches do `O(log m)` checks costing `O(n)` each; column searches do `O(log n)` checks costing `O(m)` each |
| Space | `O(1)` | Only boundary variables and helper state are used |

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

## Implementation

```python
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.

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

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

```python
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.

```python
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`.

```python
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.

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

Otherwise, the answer must be after `mid`.

```python
else:
    lo = mid + 1
```

Now we find the four boundaries.

```python
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`.

```python
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.

```python
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`.

```python
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:

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

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

## Testing

```python
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:

| Test | Why |
|---|---|
| Example matrix | General connected region |
| Single pixel | Minimum input |
| Vertical line | Height changes, width is `1` |
| Horizontal line | Width changes, height is `1` |
| Full black matrix | Rectangle covers everything |