Smallest Rectangle Enclosing Black Pixels - Lintcode

An image is represented by a binary matrix with0as a white pixel and1as 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 =, Return6.

Analysis

There are two ways to solve this: BFS and Binary Search. If the problem allows multiple black regions, then only BFS can be used. Also if the problem is asking for the areas of the black pixels which might not be connected, then only Binary Search works.

Solution for BFS

public class Point{
    int x, y;
    public Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}


public int[] deltaX = new int[]{1, 0, -1, 0};
public int[] deltaY = new int[]{0, 1, 0, -1};


public boolean isValid(char[][] image, Point point){
    if (point.x >= image.length || point.y >= image[0].length ||
        point.y < 0 || point.x < 0 || image[point.x][point.y] != '1'){
        return false;
    }    

    return true;
}

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

    //declare point lefttop and rightbottom
    Point leftTop = new Point(Integer.MAX_VALUE, Integer.MAX_VALUE);        
    Point rightBottom = new Point(Integer.MIN_VALUE, Integer.MIN_VALUE);

    //declare queue and put starting point into it        
    Queue<Point> queue = new LinkedList<Point>();
    queue.offer(new Point(x, y));

    while(!queue.isEmpty()){
        Point p = queue.poll();
        image[p.x][p.y] = '0';

        if (p.x < leftTop.x){
            leftTop.x = p.x;
        }

        if (p.x > rightBottom.x){
            rightBottom.x = p.x;
        }

        if (p.y < leftTop.y){
            leftTop.y = p.y;
        }

        if (p.y > rightBottom.y){
            rightBottom.y = p.y;
        }

        for (int i = 0; i < deltaX.length; i++){
            Point newPoint = new Point(p.x + deltaX[i], p.y + deltaY[i]);

            if (isValid(image, newPoint)){
                queue.offer(newPoint);
            }
        }            

    }

    return (rightBottom.y - leftTop.y  + 1) * (rightBottom.x - leftTop.x + 1);
}

Solution for Binary Search

public int minArea(char[][] image, int x, int y) {
    // binary search for the column left, right, row up and down

    if (image.length == 0 || image[0].length == 0) {
        return 0;
    }

    int n = image.length;
    int m = image[0].length;
    int start = y;
    int end = m - 1;

    // find column right;
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        if (checkColumn(image,  mid)){
            start = mid;
        } else {
            end = mid; 
        }
    }

    int column_right = checkColumn(image, end) ? end : start;        

    //find column left;
    start = 0;
    end = y;
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        if (checkColumn(image,  mid)){
            end = mid;
        } else {
            start = mid; 
        }
    }

    int column_left = checkColumn(image, start) ? start : end;

    //find row top
    start = 0;
    end = x;
    while (start + 1 < end){
        int mid = start + (end - start) / 2;
        if (checkRow(image, mid)){
            end = mid;
        } else {
            start = mid;
        }
    }        

    int row_top = checkRow(image, start) ? start : end;


    //find row bottom
    start = x;
    end = n;
    while (start + 1 < end){
        int mid = start + (end - start) / 2;
        if (checkRow(image, mid)){
            start = mid;
        } else {
            end = mid;
        }
    }

    int row_bottom = checkRow(image, end) ? end : start;         

    return (row_bottom - row_top + 1) * (column_right - column_left + 1);
}

public boolean checkRow(char[][] image, int row){
    if (row >= image.length){
        return false;
    }

    for (int j = 0; j < image[0].length; j++){
        if (image[row][j] == '1'){
            return true;
        }
    }
    return false;
}

public boolean checkColumn(char[][] image, int column){
    if (column >= image[0].length){
        return false;
    }        

    for (int i = 0; i < image.length; i++){
        if (image[i][column] == '1'){
            return true;
        }
    }        
    return false;
}