> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/1.binary-search/600.smallest-rectangle-enclosing-black-pixels.md).

# 600.Smallest Rectangle Enclosing Black Pixels

## 1.Description(Hard)

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.

**Example**

For example, given the following image:

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

and x =`0`, y =`2`,\
Return`6`.

## 2.Code

<http://www.cnblogs.com/grandyang/p/5268775.html>

Version 1: Binary Search

根据已有的black pixel的左边，分别找到上下左右含有1的边界，利用binary search查找。

```
 public int minArea(char[][] image, int x, int y) {
        if (image == null || image.length == 0 || image[0].length == 0) {
            return 0;
        }
        int m=image.length;
        int n=image[0].length;

        int top=searchtop(image,0,x);
        int bottom=searchbottom(image,x,m-1);
        int left=searchleft(image,0,y);
        int right=searchright(image,y,n-1);
        int area=(bottom-top+1)*(right-left+1);
        return area;
    }

    public int searchtop(char[][] image,int start,int end){

        while(start+1<end){
            int mid=start+(end-start)/2;
            if(isEmptyRow(image,mid)){
                start=mid;
            }
            else {
                end=mid;
            }
        }
        if(isEmptyRow(image,start)){
            return end;
        }
        return start;
    }
    public int searchbottom(char[][] image,int start,int end){
        while(start+1<end){
            int mid=start+(end-start)/2;
            if(isEmptyRow(image,mid)){
                end=mid;
            }
            else{
                start=mid;
            }
        }
        if(isEmptyRow(image,end)){
            return start;
        }
        return end;

    }
    public int searchleft(char[][] image,int start,int end){
        while(start+1<end){
            int mid=start+(end-start)/2;
            if(isEmptyColumn(image,mid)){
                start=mid;
            }
            else{
                end=mid;
            }
        }
        if(isEmptyColumn(image,start)){
            return end;
        }
        return start;
    }
    public int searchright(char[][] image,int start,int end){
        while(start+1<end){
            int mid=start+(end-start)/2;
            if(isEmptyColumn(image,mid)){
                end=mid;
            }
            else{
                start=mid;
            }
        }
        if(isEmptyColumn(image,end)){
            return start;
        }
        return end;
    }

    //find whether this column has '1'
    public boolean isEmptyColumn(char[][] image,int col){
        for(int i=0;i<image.length;i++){
            if(image[i][col]=='1'){
                return false;
            }
        }
        return true;
    }

    //find whether this row has '1'
    public boolean isEmptyRow(char[][] image,int row){
        for(int i=0;i<image[0].length;i++){
            if(image[row][i]=='1'){
                return false;
            }
        }
        return true;
    }
```

Version 2: Brute Force

这种方法的效率不高，遍历了整个数组，如果遇到了1，就更新矩形的返回

```
//Version 2:Brute force
public int minArea2(char[][] image, int x, int y){
    int up=x;
    int down=x;
    int left=y;
    int right=y;
    for(int i=0;i<image.length;i++){
        for(int j=0;j<image[0].length;j++){
            if(image[i][j]=='1'){
                up=Math.max(up, i);
                down=Math.min(down, i);
                left=Math.min(left,j);
                right=Math.max(right, j);
            }
        }
    }
    int area=(up-down+1)*(right-left+1);
    return area;
}
```