Smallest Rectangle Enclosing Black Pixels

Hard

Asked by:

26 views

Topics:

ArraysBinary Search

You are given a binary matrix image where 0 represents a white pixel and 1 represents a black pixel.

The black pixels are connected, i.e., there is only one black region. Pixels are connected horizontally and vertically.

Given the location (x, y) of one of the black pixels, return the area of the smallest (axis-aligned) rectangle that encloses all black pixels.

You must write an algorithm with O(m log n + n log m) runtime complexity where m is the number of rows and n is the number of columns.

Example 1:

Input: image = [["0","0","1","0"],["0","1","1","0"],["0","1","0","0"]], x = 0, y = 2
Output: 6
Explanation: The smallest rectangle enclosing the black pixels is shown in the following image.

Example 2:

Input: image = [["1"]], x = 0, y = 0
Output: 1

Example 3:

Input: image = [["0","1","0"],["1","1","1"],["0","1","0"]], x = 1, y = 1
Output: 3

Constraints:

m == image.length
n == image[i].length
1 <= m, n <= 100
image[i][j] is either '0' or '1'.
1 <= the number of black pixels <= 100
0 <= x < m
0 <= y < n
image[x][y] == '1'

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the image, and are there any constraints on the number of rows and columns?
Is the input image guaranteed to be a rectangular matrix of characters?
Can the image be empty, or contain no black pixels?
What character represents a black pixel, and what character represents a white pixel?
If there are multiple possible smallest rectangles, is any one acceptable, or is there a specific criterion for choosing one?

Brute Force Solution

Approach

The problem is to find the smallest rectangle that contains all the black pixels in an image. A brute force approach involves checking every possible rectangle that could exist within the image to see if it fits our criteria.

Here's how the algorithm would work step-by-step:

Imagine starting with a rectangle that's incredibly tiny, like just one pixel.
Move this tiny rectangle to every possible spot within the entire image, checking if it contains at least one black pixel.
Then, try rectangles that are slightly bigger - two pixels wide, two pixels tall, and so on.
Again, move each of these slightly bigger rectangles to every possible position within the image and see if any black pixels are inside.
Continue increasing the size of the rectangle and sliding it around the image, checking for black pixels each time.
As you check each rectangle size and position, remember the ones that do contain only black pixels.
Once you've tried all possible rectangle sizes and positions, look at the rectangles you've remembered, and choose the one with the smallest area. That's your answer.

Code Implementation

def smallest_rectangle_enclosing_black_pixels_brute_force(image):
    rows = len(image)
    cols = len(image[0]) if rows > 0 else 0
    min_area = float('inf')

    for top_row in range(rows):
        for left_col in range(cols):
            for bottom_row in range(top_row, rows):
                for right_col in range(left_col, cols):
                    # Iterate all possible rectangles
                    is_valid_rectangle = True
                    has_black_pixel = False

                    for row in range(top_row, bottom_row + 1):
                        for col in range(left_col, right_col + 1):
                            if image[row][col] == '1':
                                has_black_pixel = True
                                break
                        if has_black_pixel:
                            break

                    if not has_black_pixel:
                        continue

                    # We need to ensure there are no white pixels inside the rectangle
                    for row in range(rows):
                        for col in range(cols):
                            if image[row][col] == '1':
                                if not (top_row <= row <= bottom_row and \
                                        left_col <= col <= right_col):
                                    is_valid_rectangle = False
                                    break
                        if not is_valid_rectangle:
                            break

                    if is_valid_rectangle:
                        # Update min_area only if the rectangle is valid
                        area = (bottom_row - top_row + 1) * (right_col - left_col + 1)
                        min_area = min(min_area, area)

    if min_area == float('inf'):
        # No black pixels found
        return 0
    else:
        return min_area

Big(O) Analysis

Time Complexity

O(m² * n²) – Let m and n represent the dimensions of the image (rows and columns). The brute force approach iterates through all possible top-left corner positions (m * n possibilities). For each top-left corner, it considers all possible widths and heights, which, in the worst case, are also bounded by m and n respectively. Therefore, the number of possible rectangles considered is proportional to m * n * m * n, where each rectangle needs to be checked whether it contains only black pixels and encloses all the black pixels and to see if any black pixels are inside, leading to O(m² * n²) complexity.

Space Complexity

O(1) – The brute force approach, as described, primarily involves iterating through different rectangle sizes and positions. While it mentions 'remembering' rectangles that contain only black pixels, the plain English explanation does not describe the specific data structure used to store these. Assuming it only remembers the smallest rectangle found so far (i.e., the dimensions and position), it would use a constant amount of extra memory. Therefore, the auxiliary space complexity is O(1) because it does not scale with the input image size.

Optimal Solution

Approach

The problem asks for the smallest rectangle that contains all the black pixels in an image. The most efficient strategy is to use a targeted search to quickly find the boundaries of this rectangle without looking at every single pixel individually.

Here's how the algorithm would work step-by-step:

Think of the image as having top, bottom, left, and right edges that we need to find.
First, find the top edge by doing a special search in the image's rows. The key idea is that the first row containing a black pixel marks the top edge.
Similarly, locate the bottom edge by searching rows from the bottom upwards. The first row from the bottom with a black pixel is the bottom edge.
Next, search the columns from left to right to discover the left edge. The first column containing a black pixel will mark the left edge.
Finally, find the right edge by searching columns from right to left. The first column from the right containing a black pixel reveals the right edge.
Once you've found all four edges (top, bottom, left, and right), you can define the smallest rectangle that encloses all the black pixels.

Code Implementation

def smallest_rectangle_enclosing_black_pixels(image):
    number_of_rows = len(image)
    number_of_columns = len(image[0])

    def find_top_edge():
        for row_index in range(number_of_rows):
            for column_index in range(number_of_columns):
                if image[row_index][column_index] == '1':
                    return row_index

    def find_bottom_edge():
        for row_index in range(number_of_rows - 1, -1, -1):
            for column_index in range(number_of_columns):
                if image[row_index][column_index] == '1':
                    return row_index

    # Finding the leftmost column with a black pixel.
    def find_left_edge():
        for column_index in range(number_of_columns):
            for row_index in range(number_of_rows):
                if image[row_index][column_index] == '1':
                    return column_index

    def find_right_edge():
        # Searching right to left.
        for column_index in range(number_of_columns - 1, -1, -1):
            for row_index in range(number_of_rows):
                if image[row_index][column_index] == '1':
                    return column_index

    top_edge = find_top_edge()
    bottom_edge = find_bottom_edge()
    left_edge = find_left_edge()
    right_edge = find_right_edge()

    # Calculate the area using the boundaries.
    return (right_edge - left_edge + 1) * (bottom_edge - top_edge + 1)

Big(O) Analysis

Time Complexity

O(m + n) – Let m be the number of rows and n be the number of columns in the image. The algorithm performs four separate searches: top edge search (at most m rows), bottom edge search (at most m rows), left edge search (at most n columns), and right edge search (at most n columns). In the worst case, each search might iterate through all rows or columns, respectively. Thus, the overall time complexity is O(m + m + n + n), which simplifies to O(m + n).

Space Complexity

O(1) – The described algorithm aims to find the top, bottom, left, and right boundaries by iterating through rows and columns. It stores a constant number of variables representing these boundaries (top, bottom, left, right), which are updated during the search. The space used does not scale with the input image size (number of rows or columns). Therefore, the auxiliary space complexity is constant, or O(1).

Edge Cases

Case	How to Handle
Null or empty image input	Return 0 immediately as there are no pixels to enclose.
Image with zero rows or zero columns	Return 0 immediately, similar to a null or empty image.
Image with all white pixels	Return 0 since there are no black pixels to form a rectangle.
Image with only one black pixel	Return 1, as the smallest enclosing rectangle would be of size 1x1.
Image with all black pixels	Return the total area of the image (rows * cols).
Single row or single column image with black pixels	Find the first and last black pixel and calculate the length of the rectangle.
Large image where the recursion depth could exceed the stack limit (if using recursive binary search)	Convert to an iterative binary search to avoid stack overflow errors.
Integer overflow when calculating the area of the rectangle (especially with very large images)	Use a larger data type (e.g., long) for storing the area to prevent potential overflow.

Null or empty image input

How to Handle:

Return 0 immediately as there are no pixels to enclose.

Image with zero rows or zero columns

How to Handle:

Return 0 immediately, similar to a null or empty image.

Image with all white pixels

How to Handle:

Return 0 since there are no black pixels to form a rectangle.

Image with only one black pixel

How to Handle:

Return 1, as the smallest enclosing rectangle would be of size 1x1.

Image with all black pixels

How to Handle:

Return the total area of the image (rows * cols).

Single row or single column image with black pixels

How to Handle:

Find the first and last black pixel and calculate the length of the rectangle.

Large image where the recursion depth could exceed the stack limit (if using recursive binary search)

How to Handle:

Convert to an iterative binary search to avoid stack overflow errors.

Integer overflow when calculating the area of the rectangle (especially with very large images)

How to Handle:

Use a larger data type (e.g., long) for storing the area to prevent potential overflow.