Smallest Rectangle Enclosing Black Pixels

Smallest Rectangle Enclosing Black Pixels

What is this problem about?

The "Smallest Rectangle Enclosing Black Pixels" interview question is a 2D grid problem. You are given a binary matrix where '1' represents black pixels and '0' represents white pixels. All black pixels are connected. Given the coordinates of one black pixel, you need to find the area of the smallest axis-aligned rectangle that encloses all black pixels. This "Smallest Rectangle Enclosing Black Pixels coding problem" is about finding the boundaries (top, bottom, left, right) of the black pixel cluster.

Why is this asked in interviews?

Google asks this to test a candidate's ability to optimize search in a grid. While a simple BFS or DFS starting from the given pixel can find all black pixels and their boundaries in O(B) time (where B is the number of black pixels), there is a more efficient O(M log N + N log M) solution using binary search. It evaluates your ability to apply 1D search techniques (binary search) to 2D projections.

Algorithmic pattern used

This problem follows the "Binary Search and Matrix interview pattern".

• The connected property of black pixels means that if we project the pixels onto the x-axis and y-axis, the projections will be continuous intervals.
• To find the left boundary, you can binary search on the columns from 0 to y. For each column, you check if it contains any '1' by scanning that column.
• Similarly, you binary search for the right, top, and bottom boundaries.
• The area is (right - left + 1) * (bottom - top + 1).

Example explanation

Grid:

0000
0110
0100

Given pixel: (1, 1)

1. Search columns: Column 1 has a '1', column 2 has a '1'. Left=1, Right=2.
2. Search rows: Row 1 has '1', Row 2 has '1'. Top=1, Bottom=2.
3. Rect: Top-Left (1,1) to Bottom-Right (2,2). Area: (2-1+1) * (2-1+1) = 4.

Common mistakes candidates make

The most common mistake is using BFS/DFS when a faster binary search approach is possible. Another error is not correctly setting the ranges for the four binary searches. Some candidates also fail to realize that the "connected" constraint is what makes binary search applicable in the first place.

Interview preparation tip

Whenever you have a connected component in a grid and need to find its "extremes," consider whether you can binary search on the row and column projections. This "Smallest Rectangle Enclosing Black Pixels interview question" is the classic example of this optimization.