Smallest Rectangle Enclosing Black Pixels - Solution & Explanation

Problem Overview: You get a binary matrix where '1' represents a black pixel and '0' represents white. One black pixel location (x, y) is given. The task is to compute the area of the smallest axis-aligned rectangle that contains every black pixel in the image.

Approach 1: Full Grid Scan (Brute Force) (Time: O(m*n), Space: O(1))

The simplest strategy is scanning the entire grid. Track four boundaries while iterating: minRow, maxRow, minCol, and maxCol. Every time you encounter a '1', update these limits. After the scan, compute the rectangle area using (maxRow - minRow + 1) * (maxCol - minCol + 1). This approach uses only constant space and works for any matrix, but it ignores the fact that one black pixel location is already known, so it wastes time checking every cell.

Approach 2: BFS/DFS Expansion (Time: O(m*n), Space: O(m*n))

Start traversal from the known black pixel and explore all connected black pixels using breadth-first search or depth-first search. Maintain the same boundary variables while visiting each pixel. Each step checks four directions and continues only if the neighbor is also black and not yet visited. Because every black pixel is visited once, the algorithm runs in O(m*n) in the worst case. This approach leverages connectivity and avoids scanning unrelated white areas, but still degrades to full-grid exploration if most cells are black.

Approach 3: Binary Search on Boundaries (Optimal) (Time: O(m log n + n log m), Space: O(1))

The key observation: all black pixels form a connected region, so the rows and columns containing black pixels are contiguous. Instead of exploring every cell, perform binary search to locate each boundary. Search the top boundary between rows 0 and x, the bottom between x and m-1, the left between 0 and y, and the right between y and n-1. For each midpoint row or column, scan across it to check if at least one black pixel exists. Binary search narrows the first and last rows/columns containing '1'. Once boundaries are found, compute the rectangle area. This approach dramatically reduces search space compared with full traversal.

Recommended for interviews: The binary search boundary approach is usually what interviewers expect. It shows you recognized the monotonic property of rows and columns containing black pixels. Mentioning the brute force or BFS/DFS first demonstrates understanding of the grid traversal baseline, but implementing the binary search version proves stronger algorithmic insight with better asymptotic performance.