Solution: Smallest Rectangle Enclosing Black Pixels
Let’s solve the Smallest Rectangle Enclosing Black Pixels problem using the Matrices pattern.
We'll cover the following
Statement
You are given an image
, where
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
.
Constraints:
image.length
== image[i].length
image[i][j]
is eitheror x
y
image[x][y]
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:
Helper functions for identifying black pixels:
We define two helper functions:ContainsBlackPixelInColumn(mid)
: Checks if a specific column contains any black pixel (‘1’) by iterating over all rows.ContainsBlackPixelInRow(mid)
: Checks if a specific row contains any black pixel by verifying if ‘1’ exists in that row.
Finding boundaries using binary search:
We employ a binary search approach to find the smallest rectangle that encloses all black pixels:Left boundary:
We search for the leftmost column containing a black pixel within the range[0, y]
. We useBinarySearch
with theContainsBlackPixelInColumn
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.Right boundary:
We search for the rightmost column containing a black pixel within the range[y + 1, n)
. TheBinarySearch
function here uses a lambda function that negatesContainsBlackPixelInColumn
to stop at the first column without a black pixel. We subtract 1 from the result to get the correct right boundary.Top boundary:
We search for the topmost row with a black pixel within the range[0, x]
usingBinarySearch
andContainsBlackPixelInRow
as the condition checker.Bottom boundary:
We search for the bottommost row with a black pixel within the range[x + 1, m)
using a lambda function that negatesContainsBlackPixelInRow
. Again, we subtract 1 from the result to get the correct bottom boundary.
Calculating the area:
Once all four boundaries are determined, calculate the area of the smallest rectangle that encloses all black pixels using the formula:
Level up your interview prep. Join Educative to access 70+ hands-on prep courses.