# 302    Smallest Rectangle Enclosing Black Pixels

## 302. [Smallest Rectangle Enclosing Black Pixels](https://leetcode.com/problems/smallest-rectangle-enclosing-black-pixels/description/)

## 1. Question

An image is represented by a binary matrix with`0`as a white pixel and`1`as a black pixel. The black pixels are connected, i.e., there is only one black region. Pixels are connected horizontally and vertically. Given the location`(x, y)`of one of the black pixels, return the area of the smallest (axis-aligned) rectangle that encloses all black pixels.

For example, given the following image:

```
[
  "0010",
  "0110",
  "0100"
]
```

and`x = 0`,`y = 2`,

Return`6`.

## 2. Implementation

**(1) Binary Search**

```java
class Solution {
    public int minArea(char[][] image, int x, int y) {
        int m = image.length, n = image[0].length;

        int left = lowerBound(image, 0, y, false);
        int right = upperBound(image, y, n - 1, false);
        int top = lowerBound(image, 0, x, true);
        int bottom = upperBound(image, x, m - 1, true);

        return (right - left + 1) * (bottom - top + 1);
    }

    public int lowerBound(char[][] image, int start, int end, boolean searchInRow) {
        int mid = 0;

        while (start + 1 < end) {
            mid = start + (end - start) / 2;
            if (!isBlackPixel(image, mid, searchInRow)) {
                start = mid + 1;
            }
            else {
                end = mid;
            }
        }

        if (isBlackPixel(image, start, searchInRow)) {
            return start;
        }
        else {
            return end;
        }
    }

    public int upperBound(char[][] image, int start, int end, boolean searchInRow) {
        int mid = 0;

        while (start + 1 < end) {
            mid = start + (end - start) / 2;
            if (!isBlackPixel(image, mid, searchInRow)) {
                end = mid - 1;
            }
            else {
                start = mid;
            }
        }

        if (isBlackPixel(image, end, searchInRow)) {
            return end;
        }
        else {
            return start;
        }
    }

    public boolean isBlackPixel(char[][] image, int index, boolean searchInRow) {
        if (searchInRow) {
            for (int col = 0; col < image[0].length; col++) {
                if (image[index][col] == '1') {
                    return true;
                }
            }
        }
        else {
            for (int row = 0; row < image.length; row++) {
                if (image[row][index] == '1') {
                    return true;
                }
            }
        }
        return false;
    }
}
```

## 3. Time & Space Complexity

**Binary Search:** 时间复杂度: O(mlogn + nlogm), 空间复杂度O(1)