Smallest Rectangle Enclosing Black Pixels

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.

For example, given the following image:

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

andx = 0,y = 2, Return6.

Solution #1:

Starting from the given point, DFS to its left, right, up and down, and update max and min coordinates accordingly. If the navigated point is 0, stop. If it is 1, change the character to something else to prevent infinite loop. At the end, calculate area by multiply length by width.

public int minArea(char[][] image, int x, int y) {
    int[] records = new int[4];
    records[0] = x;
    records[1] = x;
    records[2] = y;
    records[3] = y;
    getXY(x, y, image, records);
    return (records[1] - records[0] + 1) * (records[3] - records[2] + 1);
}
private void getXY(int x, int y, char[][] image, int[] records) {
    if (x < 0 || x >= image.length || y < 0 || y >= image[0].length) {
        return;
    }
    if (image[x][y] == '1') {
        image[x][y] = '2';
        records[0] = Math.min(records[0], x);
        records[1] = Math.max(records[1], x);
        records[2] = Math.min(records[2], y);
        records[3] = Math.max(records[3], y);
        getXY(x + 1, y, image, records);
        getXY(x - 1, y, image, records);
        getXY(x, y + 1, image, records);
        getXY(x, y - 1, image, records);
    } else {
        return;
    }
}

Solution #2:

Use binary search to find out the first/last column that contains a 1 in it, and then find out the first/last row that contains a 1 in it. Then calculate width and height to get smallest area.

public int minArea(char[][] image, int x, int y) {
    if (image == null || image.length == 0 || image[0] == null || image[0].length == 0) {
        return 0;
    }
    int left   = findLeft(image, 0, y);
    int right  = findRight(image, y, image[0].length - 1);
    int top    = findTop(image, 0, x);
    int bottom = findBottom(image, x, image.length - 1);
    return (right - left + 1) * (bottom - top + 1);
}
//find first column has '1' in this row
private int findLeft(char[][] image, int left, int right) {
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (isEmptyColumn(image, mid)) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}
//find last column has '1' int this row
private int findRight(char[][] image, int left, int right) {
    int lastIndex = left;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (isEmptyColumn(image, mid)) {
            right = mid - 1;
        } else {
            lastIndex = mid;
            left = mid + 1;
        }
    }
    return lastIndex;
}
private int findTop(char[][] image, int left, int right) {
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (isEmptyRow(image, mid)) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}
private int findBottom(char[][] image, int left, int right) {
    int lastIndex = left;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (isEmptyRow(image, mid)) {
            right = mid - 1;
        } else {
            lastIndex = mid;
            left = mid + 1;
        }
    }
    return lastIndex;
}
private boolean isEmptyColumn(char[][] image, int col) {
    for (int i = 0; i < image.length; i++) {
        if (image[i][col] == '1') {
            return false;
        }
    }
    return true;
}
private boolean isEmptyRow(char[][] image, int row) {
    for (int i = 0; i < image[0].length; i++) {
        if (image[row][i] == '1') {
            return false;
        }
    }
    return true;
}