Solution: Smallest Rectangle Enclosing Black Pixels

Statement

You are given an $m \times n$ binary matrix image, where $0$ represents a white pixel and $1$ represents a black pixel.

All black pixels in the matrix form a single connected region, where connectivity is defined by horizontal or vertical adjacency.

Given two integers x and y that represent the coordinates of one of the black pixels, write an algorithm to find the area of the smallest axis-aligned rectangle that encloses all the black pixels.

Note: Your solution must have a runtime complexity less than $O(m \times n)$.

Constraints:

• $m$ $==$ image.length

• $n$ == image[i].length

• $1 \leq m, n \leq 100$

• image[i][j] is either $0$ or $1$

• $0 \leq$ x $< m$

• $0 \leq$ y $< n$

• image[x][y] $== 1$

• The black pixels in the image only form one component.

Solution

The key intuition behind this solution is to treat the given 2D binary matrix as a series of row and column vectors. The properties of matrices allow us to "project" this 2D image onto 1D arrays. By projecting the image, we essentially compress the entire 2D matrix into separate row and column arrays, capturing the presence of black pixels in each row and column.

Since all black pixels in each row and column are connected, we can apply binary search on the rows and columns to find the boundaries. By combining matrix properties with binary search, we can avoid a full traversal of the entire matrix, achieving a more optimal solution.

Here is the step by step explanation of the solution:

1. Helper functions for identifying black pixels:
   We define two helper functions:

   1. contains_black_pixel_in_column(mid): Checks if a specific column contains any black pixel (‘1’) by iterating over all rows.

   2. contains_black_pixel_in_row(mid): Checks if a specific row contains any black pixel by verifying if ‘1’ exists in that row.

2. Finding boundaries using binary search:
   We employ a binary search approach to find the smallest rectangle that encloses all black pixels:

   1. Left boundary:
      We search for the leftmost column containing a black pixel within the range [0, y]. We use binary_search with the contains_black_pixel_in_column function as the condition checker. If a column contains a black pixel, it becomes the right end of our search range, narrowing down the left boundary.

   2. Right boundary:
      We search for the rightmost column containing a black pixel within the range [y + 1, n). The binary_search function here uses a lambda function that negates contains_black_pixel_in_column to stop at the first column without a black pixel. We subtract 1 from the result to get the correct right boundary.

   3. Top boundary:
      We search for the topmost row with a black pixel within the range [0, x] using binary_search and contains_black_pixel_in_row as the condition checker.

   4. Bottom boundary:
      We search for the bottommost row with a black pixel within the range [x + 1, m) using a lambda function that negates contains_black_pixel_in_row. Again, we subtract 1 from the result to get the correct bottom boundary.

3. Calculating the area:
   Once all four boundaries are determined, calculate the area of the smallest rectangle that encloses all black pixels using the formula: