302. Smallest Rectangle Enclosing Black Pixels


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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

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

1image = [
2  [0, 0, 1, 0, 0],
3  [0, 1, 1, 1, 0],
4  [0, 0, 1, 0, 0],
5  [0, 0, 0, 0, 0]
6]
7x = 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

1from typing import List
2
3class Solution:
4    def minArea(self, image: List[List[str]], x: int, y: int) -> int:
5        # Get the number of rows and columns
6        num_rows, num_cols = len(image), len(image[0])
7
8        # Binary search to find the upper boundary
9        top, bottom = 0, x
10        while top < bottom:
11            mid = (top + bottom) // 2
12            if '1' in image[mid]:
13                bottom = mid
14            else:
15                top = mid + 1
16        upper_bound = top
17
18        # Binary search to find the lower boundary
19        top, bottom = x, num_rows - 1
20        while top < bottom:
21            mid = (top + bottom + 1) // 2
22            if '1' in image[mid]:
23                top = mid
24            else:
25                bottom = mid - 1
26        lower_bound = top
27
28        # Binary search to find the left boundary
29        left, right = 0, y
30        while left < right:
31            mid = (left + right) // 2
32            if any(row[mid] == '1' for row in image):
33                right = mid
34            else:
35                left = mid + 1
36        left_bound = left
37
38        # Binary search to find the right boundary
39        left, right = y, num_cols - 1
40        while left < right:
41            mid = (left + right + 1) // 2
42            if any(row[mid] == '1' for row in image):
43                left = mid
44            else:
45                right = mid - 1
46        right_bound = left
47
48        # Calculate the area of the minimum rectangle enclosing the black pixels
49        height = lower_bound - upper_bound + 1
50        width = right_bound - left_bound + 1
51        return height * width
52
1class Solution {
2    public int minArea(char[][] image, int x, int y) {
3        int numRows = image.length;
4        int numCols = image[0].length;
5      
6        // Binary search to find the top boundary of the rectangle
7        int top = binarySearchTop(image, 0, x, numCols);
8        // Binary search to find the bottom boundary of the rectangle
9        int bottom = binarySearchBottom(image, x, numRows - 1, numCols);
10        // Binary search to find the left boundary of the rectangle
11        int left = binarySearchLeft(image, 0, y, numRows);
12        // Binary search to find the right boundary of the rectangle
13        int right = binarySearchRight(image, y, numCols - 1, numRows);
14
15        // Calculating the area of the rectangle
16        return (bottom - top + 1) * (right - left + 1);
17    }
18  
19    private int binarySearchTop(char[][] image, int startRow, int endRow, int numCols) {
20        while(startRow < endRow) {
21            int midRow = startRow + (endRow - startRow) / 2;
22            if (containsBlackPixel(image[midRow], numCols)) {
23                endRow = midRow;
24            } else {
25                startRow = midRow + 1;
26            }
27        }
28        return startRow;
29    }
30  
31    private int binarySearchBottom(char[][] image, int startRow, int endRow, int numCols) {
32        while(startRow < endRow) {
33            int midRow = startRow + (endRow - startRow + 1) / 2;
34            if (containsBlackPixel(image[midRow], numCols)) {
35                startRow = midRow;
36            } else {
37                endRow = midRow - 1;
38            }
39        }
40        return startRow;
41    }
42  
43    private int binarySearchLeft(char[][] image, int startCol, int endCol, int numRows) {
44        while(startCol < endCol) {
45            int midCol = startCol + (endCol - startCol) / 2;
46            if (containsBlackPixelInColumn(image, midCol, numRows)) {
47                endCol = midCol;
48            } else {
49                startCol = midCol + 1;
50            }
51        }
52        return startCol;
53    }
54  
55    private int binarySearchRight(char[][] image, int startCol, int endCol, int numRows) {
56        while(startCol < endCol) {
57            int midCol = startCol + (endCol - startCol + 1) / 2;
58            if (containsBlackPixelInColumn(image, midCol, numRows)) {
59                startCol = midCol;
60            } else {
61                endCol = midCol - 1;
62            }
63        }
64        return startCol;
65    }
66  
67    // Helper method to check if a row contains a black pixel
68    private boolean containsBlackPixel(char[] row, int numCols) {
69        for (int i = 0; i < numCols; i++) {
70            if (row[i] == '1') {
71                return true;
72            }
73        }
74        return false;
75    }
76  
77    // Helper method to check if a column contains a black pixel
78    private boolean containsBlackPixelInColumn(char[][] image, int col, int numRows) {
79        for (int i = 0; i < numRows; i++) {
80            if (image[i][col] == '1') {
81                return true;
82            }
83        }
84        return false;
85    }
86}
87
1class Solution {
2public:
3    int minArea(vector<vector<char>>& image, int x, int y) {
4        // Get the dimensions of the image
5        int numRows = image.size(), numCols = image[0].size();
6      
7        // Binary search to find the top boundary of the black pixels
8        int top = 0, bottom = x;
9        while (top < bottom) {
10            int mid = top + (bottom - top) / 2;
11            int col = 0;
12            while (col < numCols && image[mid][col] == '0') ++col;
13            if (col < numCols)
14                bottom = mid; // Black pixel found, move bottom up
15            else
16                top = mid + 1; // No black pixel, move top down
17        }
18        int upperBound = top; // Top boundary found
19      
20        // Binary search to find the bottom boundary of the black pixels
21        top = x;
22        bottom = numRows - 1;
23        while (top < bottom) {
24            int mid = top + (bottom - top + 1) / 2;
25            int col = 0;
26            while (col < numCols && image[mid][col] == '0') ++col;
27            if (col < numCols)
28                top = mid; // Black pixel found, move top down
29            else
30                bottom = mid - 1; // No black pixel, move bottom up
31        }
32        int lowerBound = top; // Bottom boundary found
33      
34        // Binary search to find the left boundary of the black pixels
35        int left = 0, right = y;
36        while (left < right) {
37            int mid = left + (right - left) / 2;
38            int row = 0;
39            while (row < numRows && image[row][mid] == '0') ++row;
40            if (row < numRows)
41                right = mid; // Black pixel found, move right left
42            else
43                left = mid + 1; // No black pixel, move left right
44        }
45        int leftBound = left; // Left boundary found
46      
47        // Binary search to find the right boundary of the black pixels
48        left = y;
49        right = numCols - 1;
50        while (left < right) {
51            int mid = left + (right - left + 1) / 2;
52            int row = 0;
53            while (row < numRows && image[row][mid] == '0') ++row;
54            if (row < numRows)
55                left = mid; // Black pixel found, move left right
56            else
57                right = mid - 1; // No black pixel, move right left
58        }
59        int rightBound = left; // Right boundary found
60      
61        // Compute and return the area of the rectangle enclosing the black pixels
62        return (lowerBound - upperBound + 1) * (rightBound - leftBound + 1);
63    }
64};
65
1function minArea(image: string[][], x: number, y: number): number {
2    // Get the number of rows and columns of the image
3    const numRows: number = image.length;
4    const numCols: number = image[0].length;
5
6    // Binary search to find the top boundary of the black pixels
7    let top: number = 0;
8    let bottom: number = x;
9    while (top < bottom) {
10        const mid: number = top + Math.floor((bottom - top) / 2);
11        let col: number = 0;
12        while (col < numCols && image[mid][col] === '0') col++;
13        if (col < numCols)
14            bottom = mid; // Found a black pixel, adjust the bottom boundary upwards
15        else
16            top = mid + 1; // No black pixels found, adjust the top boundary downwards
17    }
18    const upperBound: number = top; // Finalized top boundary
19
20    // Binary search to find the bottom boundary of the black pixels
21    top = x;
22    bottom = numRows - 1;
23    while (top < bottom) {
24        const mid: number = top + Math.ceil((bottom - top) / 2);
25        let col: number = 0;
26        while (col < numCols && image[mid][col] === '0') col++;
27        if (col < numCols)
28            top = mid; // Found a black pixel, adjust the top boundary downwards
29        else
30            bottom = mid - 1; // No black pixels found, adjust the bottom boundary upwards
31    }
32    const lowerBound: number = top; // Finalized bottom boundary
33
34    // Binary search to find the left boundary of the black pixels
35    let left: number = 0;
36    let right: number = y;
37    while (left < right) {
38        const mid: number = left + Math.floor((right - left) / 2);
39        let row: number = 0;
40        while (row < numRows && image[row][mid] === '0') row++;
41        if (row < numRows)
42            right = mid; // Found a black pixel, adjust the right boundary leftward
43        else
44            left = mid + 1; // No black pixels found, adjust the left boundary rightward
45    }
46    const leftBound: number = left; // Finalized left boundary
47
48    // Binary search to find the right boundary of the black pixels
49    left = y;
50    right = numCols - 1;
51    while (left < right) {
52        const mid: number = left + Math.ceil((right - left) / 2);
53        let row: number = 0;
54        while (row < numRows && image[row][mid] === '0') row++;
55        if (row < numRows)
56            left = mid; // Found a black pixel, adjust the left boundary rightward
57        else
58            right = mid - 1; // No black pixels found, adjust the right boundary leftward
59    }
60    const rightBound: number = left; // Finalized right boundary
61
62    // Compute and return the area of the rectangle enclosing the black pixels
63    return (lowerBound - upperBound + 1) * (rightBound - leftBound + 1);
64}
65

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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

You are given an array of intervals where intervals[i] = [start_i, end_i] represent the start and end of the ith interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.