Problem Description

You are provided with a binary matrix called image with dimensions m x n, where 0 represents a white pixel and 1 represents a black pixel. All black pixels are connected, meaning there is only one black region, and pixels within this region are connected either horizontally or vertically. You are also given two integers, x and y, which represent the coordinates of one of the black pixels in the matrix.

Your task is to compute the smallest area of an axis-aligned rectangle that contains all the black pixels. The challenge is to design an algorithm to find this area that runs in less than O(mn) time complexity.

Flowchart Walkthrough

To find the best algorithm for solving Leetcode 302. Smallest Rectangle Enclosing Black Pixels, let’s utilize the decision-making process depicted in the Flowchart. We’ll assess if and how Depth-First Search (DFS) may be applicable. Here’s the logical step-by-step analysis:

Is it a graph?

• Yes: The image can be regarded as a graph with pixels as nodes. Nodes (pixels) are connected to their immediate neighbors (up, down, left, right) that are also black.

Is it a tree?

• No: The graph represented by the image is not necessarily a tree because multiple pixel connections are possible without a strict hierarchical structure.

Is the problem related to directed acyclic graphs (DAGs)?

• No: This problem does not involve any directional dependence among pixels that restricts cyclic dependencies; it is more about spatial relationships.

Is the problem related to shortest paths?

• No: The challenge is to find the smallest enclosing rectangle, not a path.

Does the problem involve connectivity?

• Yes: Identifying how black pixels connect to form blocks or clusters is crucial in determining the bounds of the minimum enclosing rectangle.

Does the problem have small constraints?

• Yes: Given typical image sizes and concerns about efficiency, methods that effectively traverse and examine local structures (like DFS) are applicable.

Conclusion: According to the flowchart, the problem's characteristics strongly point towards utilizing DFS or BFS due to local connectivity-based operations required to determine the smallest enclosing rectangle. DFS is particularly suitable for exploring and marking extents of connected components in a detailed manner, useful for delineating the rectangle boundaries. Thus, DFS would be an appropriate choice for implementing the solution to efficiently highlight connected black pixels and determine the rectangle bounds.

Intuition

For this problem, we need to find the boundaries of the rectangle (leftmost, rightmost, topmost, bottommost edges) that encloses all the black pixels.

The intuition behind the solution is to use binary search to efficiently find these edges. Instead of scanning the entire matrix, which would result in an O(mn) solution, binary search allows us to significantly reduce the number of pixels we look at to determine the boundaries. Since we know the black pixels are connected and form a single region, we can search in each direction—up, down, left, right—to find how far the black pixels extend.

For each direction, we apply binary search:

1. Up (topmost edge): We start from the given black pixel and move upwards, row by row. If we find a row that contains black pixels, we continue searching above it; if not, we move downwards.
2. Down (bottommost edge): We start from the given black pixel and move downwards.
3. Left (leftmost edge): We start from the given black pixel and move left, column by column.
4. Right (rightmost edge): We start from the given black pixel and move right.

By doing this, we can find the minimum and maximum rows and columns that contain black pixels, which define the rectangle's boundaries. Once we have the boundaries, calculating the area is straightforward: by multiplying the width (right - left + 1) by the height (bottom - top + 1).

The reason why binary search works here and is more efficient than scanning is that it narrows down the searching range by half with each step, thus drastically reducing the number of necessary operations.

Learn more about Depth-First Search, Breadth-First Search and Binary Search patterns.

Solution Approach

The implementation follows the intuition behind the solution, applying binary search to find the four edges of the smallest rectangle enclosing all black pixels. The binary search algorithm is used four times, once for each direction: up, down, left, and right.

The binary search steps for each direction can be broken down as follows:

• Up (Top Edge): Initialize left to 0 and right to x. Use binary search between left and right. For each mid row, check if there is any black pixel in that row by scanning all columns from 0 to n-1. If a black pixel is found (image[mid][c] == '1'), then this row could potentially be the top edge, so we bring the right pointer to mid. If no black pixel is found, shift the left pointer to mid + 1. Continue until left and right converge to the topmost row containing a black pixel.

• Down (Bottom Edge): Initialize left to x and right to m - 1. Use binary search again. If a black pixel is found in the mid row, then this row could potentially be the bottom edge, so we update left to mid. If none are found, we shift right to mid - 1. Repeat until left and right converge to the bottommost row containing a black pixel.

• Left (Left Edge): Initialize left to 0 and right to y. Apply binary search between these two pointers. For each mid column, check all rows to see if a black pixel is present. If so, right is updated to mid. Otherwise, move left to mid + 1. This will continue until we find the leftmost column with a black pixel.

• Right (Right Edge): Initialize left to y and right to n - 1 and apply binary search. If a black pixel is found in the mid column, then update left to mid; if not, update right to mid - 1. Repeat until left and right converge to the rightmost column with a black pixel.

Once all four edges of the rectangle are found, the area can be calculated by multiplying the number of rows in the height (d - u + 1, where u is the up edge and d is the down edge) by the number of columns in the width (r - l + 1, where l is the left edge and r is the right edge).

This approach efficiently narrows down the boundaries of the enclosing rectangle using binary search with a time complexity of O(log m + log n), which is a significant improvement over the brute force O(mn) solution. Here, the constant factors depend on the dimension of the input that is being halved in each binary search step, either the height (m) or the width (n) of the binary matrix.

Example Walkthrough

Let's assume we have a binary matrix image and the pixel coordinates (x, y) as shown below:

image = [
  [0, 0, 1, 0, 0],
  [0, 1, 1, 1, 0],
  [0, 0, 1, 0, 0],
  [0, 0, 0, 0, 0]
]
x = 1, y = 2

The aim is to find the smallest rectangle that encloses the black pixels, where 0 represents a white pixel and 1 represents a black pixel.

Top Edge (Up)

• We start looking for the top edge by initializing left at 0 and right at the x coordinate, which is 1.
• During the binary search, we check the middle row for black pixels by scanning all the columns.
• Initially, mid is (0 + 1) / 2 = 0 since we round down if needed. We find black pixels in row 0.
• We move right to mid, which is now 0.
• left and right converge to row 0, which becomes our top edge.

Bottom Edge (Down)

• For the bottom edge, we initialize left at x (1) and right at m - 1 (3).
• The first mid is (1 + 3) / 2 = 2. There is a black pixel at row 2.
• Hence, we shift left to mid, which is 2.
• No more movement is possible, and left and right converge to row 2 which is our bottom edge.

Left Edge

• To find the left edge, we start with left at 0 and right at y (2).
• The first mid is between column 0 and 2, so it is 1.
• Since column 1 has a black pixel, we move right to mid, which is 1.
• The next mid is (0 + 1) / 2 = 0, but column 0 has no black pixels so we move left to mid + 1 which is 1.
• left and right converge at 1, so our left edge is column 1.

Right Edge

• We search for the right edge with left at y (2) and right at n - 1 (4).
• The initial mid is (2 + 4) / 2 = 3.
• Even though column 3 has no black pixels, we don't move left because it already has the correct value (y), we move right to mid - 1, which is 2.
• left and right converge at 2, defining our right edge which is column 2.

Having found the boundaries, we can calculate the enclosing rectangle's area. The width is right - left + 1 = 2 - 1 + 1 = 2 and the height is bottom - top + 1 = 2 - 0 + 1 = 3. Therefore, the area is width * height = 2 * 3 = 6.

The above method efficiently uses binary search to determine the boundaries without scanning the entire m x n matrix, thus providing a solution with better time complexity than O(mn).

Solution Implementation

Time and Space Complexity

The provided code performs a binary search in four directions: up, down, left, and right to find the boundaries of the smallest rectangle containing all the '1's in a given binary matrix image.

For the up direction, the time complexity is O(log(m) * n) where m is the number of rows in image and n is the number of columns. This is because the binary search is done vertically across rows taking O(log(m)) and for each row, we might have to check up to n columns.

For the down direction, the computation is likewise O(log(m) * n).

For the left direction, we perform a binary search horizontally, which takes O(log(n)) and for each column, it checks up to m rows, yielding a time complexity of O(log(n) * m).

Similarly, for the right direction, we have a time complexity of O(log(n) * m).

Since the binary searches are independent of each other, the highest time complexity is what determines the total time complexity. Adding the complexities of each direction, two of which are O(log(m) * n) and the other two are O(log(n) * m), it remains in the worst case O(log(m) * n + log(n) * m). However, since generally log(m) * n and log(n) * m will be dominated by max(m, n), the total time complexity can be simplified and represented as O(log(max(m, n)) * max(m, n)).

The space complexity is O(1) since the space required does not depend on the input size but only on a few pointers and indices used for running the binary searches.

Learn more about how to find time and space complexity quickly using problem constraints.