Smallest Rectangle Enclosing Black Pixels

Problem Statement

In this problem, you are provided with a binary matrix named image of dimensions m x n where each entry is either 0 or 1. Here, 0 indicates a white pixel, whereas 1 indicates a black pixel. All black pixels present in the matrix form a singular connected region, connected by their edges (not diagonally).

Given a specific pixel location (x, y) within this matrix which is black (image[x][y] == '1'), your task is to compute the area (in terms of the number of pixels) of the smallest rectangle that can encompass all the black pixels entirely. This rectangle must be aligned with the axes of the matrix.

Additionally, the solution you devise should strive for an efficiency better than O(mn) in terms of runtime complexity.

Examples

Example 1

Input:

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

Output:

6

Example 2

Input:

image = [["1"]], x = 0, y = 0

Output:

1

Constraints

• m == image.length
• n == image[i].length
• 1 <= m, n <= 100
• image[i][j] is either '0' or '1'.
• 0 <= x < m
• 0 <= y < n
• image[x][y] == '1'.
• The black pixels in the image only form one component.

Approach and Intuition

Following a deeper dive into the examples and constraints provided, here's a structured approach to solve the problem:

1. Bounding Box Calculation:

   • To determine the smallest rectangle enclosing all black pixels, compute the minimum and maximum x (rows) and y (columns) coordinates that include black pixels. This identifies the rectangle's bounding box.

2. Efficient Scanning:

   • To comply with the complexity constraint of less than O(mn), consider methods like binary search on rows and columns independently to find the exact bounds of black pixels.
   • Since image[x][y] is guaranteed to be 1, this can serve as a starting point for such searches.

3. Example Evaluation:

   • Example 1:

     • The given matrix is [[0,0,1,0],[0,1,1,0],[0,1,0,0]] with starting black pixel at (0, 2).
     • Minimum bounding coordinates can be calculated as top = 0, bottom = 2, left = 1, and right = 2.
     • The area of the enclosed rectangle is (bottom - top + 1) * (right - left + 1) = 3 * 2 = 6.

   • Example 2:

     • For a matrix [[1]] with starting black pixel at (0, 0), the entire single-pixel matrix is the bounding box.
     • Thus, the area is 1.

This methodology not only pinpoints the necessary computations but also ensures they are carried out efficiently, avoiding a brute-force search across all elements of the matrix.

Solutions

public class Solution {
    public int minimumArea(char[][] grid, int x, int y) {
        int rows = grid.length, cols = grid[0].length;
        int minCol = findCols(grid, 0, y, 0, rows, true);
        int maxCol = findCols(grid, y + 1, cols, 0, rows, false);
        int minRow = findRows(grid, 0, x, minCol, maxCol, true);
        int maxRow = findRows(grid, x + 1, rows, minCol, maxCol, false);
        return (maxCol - minCol) * (maxRow - minRow);
    }
    private int findCols(char[][] grid, int start, int end, int top, int bottom, boolean findBlack) {
        while (start != end) {
            int mid = (start + end) / 2, row = top;
            while (row < bottom && grid[row][mid] == '0') ++row;
            if (row < bottom == findBlack)
                end = mid;
            else
                start = mid + 1;
        }
        return start;
    }
    private int findRows(char[][] grid, int start, int end, int left, int right, boolean findBlack) {
        while (start != end) {
            int mid = (start + end) / 2, col = left;
            while (col < right && grid[mid][col] == '0') ++col;
            if (col < right == findBlack)
                end = mid;
            else
                start = mid + 1;
        }
        return start;
    }
}