LeetCode Solutions Blog

Smallest Rectangle Enclosing Black Pixels

Number: 302

Difficulty: Hard

Paid? Yes

Companies: Google

Problem Description

Given an m x n binary matrix where '0' represents a white pixel and '1' a black pixel, and knowing that all black pixels form a single connected component, determine the area of the smallest axis-aligned rectangle that encloses all black pixels. A black pixel's coordinate (x, y) is provided as an input, and the solution must run in less than O(m*n) time.

Key Insights

The black pixels are connected in one region, ensuring a continuous block.
Instead of scanning every pixel, binary search can be applied on rows and columns to find boundaries.
The challenge is to efficiently determine the topmost, bottommost, leftmost, and rightmost rows/columns that contain a black pixel.

Space and Time Complexity

Time Complexity: O(mlogn + nlogm)
Space Complexity: O(1)

Solution

The approach uses four binary searches to find the extreme boundaries:

Search for the left boundary: the smallest column index with a black pixel.
Search for the right boundary: the largest column index with a black pixel.
Search for the top boundary: the smallest row index with a black pixel.
Search for the bottom boundary: the largest row index with a black pixel.

For each binary search, we check if a row/column contains any black pixel and update search bounds accordingly. The area is then calculated as: Area = (right boundary - left boundary + 1) * (bottom boundary - top boundary + 1)

This method leverages the sorted nature of row and column indices (via binary search), resulting in a performance better than scanning every cell.

Code Solutions

# Python solution with line-by-line comments

class Solution:
    def minArea(self, image, x, y):
        # Extract dimensions of the image
        m, n = len(image), len(image[0])
        
        # Helper function to check if a column has any black pixel
        def hasBlackInCol(col):
            for i in range(m):
                if image[i][col] == '1':
                    return True
            return False
        
        # Helper function to check if a row has any black pixel
        def hasBlackInRow(row):
            return '1' in image[row]
        
        # Binary search for left boundary (minimum column with a black pixel)
        left, right = 0, y
        while left < right:
            mid = (left + right) // 2
            if hasBlackInCol(mid):
                right = mid
            else:
                left = mid + 1
        leftBoundary = left
        
        # Binary search for right boundary (maximum column with a black pixel)
        left, right = y, n - 1
        while left < right:
            mid = (left + right + 1) // 2  # bias towards right
            if hasBlackInCol(mid):
                left = mid
            else:
                right = mid - 1
        rightBoundary = left
        
        # Binary search for top boundary (minimum row with a black pixel)
        top, bottom = 0, x
        while top < bottom:
            mid = (top + bottom) // 2
            if hasBlackInRow(mid):
                bottom = mid
            else:
                top = mid + 1
        topBoundary = top
        
        # Binary search for bottom boundary (maximum row with a black pixel)
        top, bottom = x, m - 1
        while top < bottom:
            mid = (top + bottom + 1) // 2  # bias towards bottom
            if hasBlackInRow(mid):
                top = mid
            else:
                bottom = mid - 1
        bottomBoundary = top
        
        # Calculate the area of the rectangle
        area = (rightBoundary - leftBoundary + 1) * (bottomBoundary - topBoundary + 1)
        return area