Solution: Smallest Rectangle Enclosing Black Pixels
Explore how to determine the area of the smallest axis-aligned rectangle enclosing all connected black pixels in a binary matrix. Learn to apply matrix projections and binary search on rows and columns to optimize the solution beyond brute force methods. This lesson guides you through using helper functions and boundary detection to achieve efficient runtime and constant space 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:
...