302. Smallest Rectangle Enclosing Black Pixels

HardDepth-First SearchBreadth-First SearchArrayBinary SearchMatrix
Leetcode Link

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.

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

A heap is a ...?

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is a min heap?

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
Not Sure What to Study? Take the 2-min Quiz：

Which two pointer techniques do you use to check if a string is a palindrome?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a good use case for backtracking?

Recommended Readings

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

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

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫