Solution: Smallest Rectangle Enclosing Black Pixels
Explore how to identify the smallest axis-aligned rectangle enclosing all black pixels in a binary matrix. Learn to apply binary search on rows and columns by projecting the matrix into 1D arrays. Understand how this reduces runtime below O(m × n) by efficiently locating boundaries, enabling you to solve matrix traversal problems with reduced complexity.
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:
...