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:
- 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.
- Down (bottommost edge): We start from the given black pixel and move downwards.
- Left (leftmost edge): We start from the given black pixel and move left, column by column.
- 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
to0
andright
tox
. Use binary search betweenleft
andright
. For eachmid
row, check if there is any black pixel in that row by scanning all columns from0
ton-1
. If a black pixel is found (image[mid][c] == '1'
), then this row could potentially be the top edge, so we bring theright
pointer tomid
. If no black pixel is found, shift theleft
pointer tomid + 1
. Continue untilleft
andright
converge to the topmost row containing a black pixel. -
Down (Bottom Edge): Initialize
left
tox
andright
tom - 1
. Use binary search again. If a black pixel is found in themid
row, then this row could potentially be the bottom edge, so we updateleft
tomid
. If none are found, we shiftright
tomid - 1
. Repeat untilleft
andright
converge to the bottommost row containing a black pixel. -
Left (Left Edge): Initialize
left
to0
andright
toy
. Apply binary search between these two pointers. For eachmid
column, check all rows to see if a black pixel is present. If so,right
is updated tomid
. Otherwise, moveleft
tomid + 1
. This will continue until we find the leftmost column with a black pixel. -
Right (Right Edge): Initialize
left
toy
andright
ton - 1
and apply binary search. If a black pixel is found in themid
column, then updateleft
tomid
; if not, updateright
tomid - 1
. Repeat untilleft
andright
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 EvaluatorExample 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
at0
andright
at thex
coordinate, which is1
. - 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 row0
. - We move
right
tomid
, which is now0
. left
andright
converge to row0
, which becomes our top edge.
Bottom Edge (Down)
- For the bottom edge, we initialize
left
atx
(1
) andright
atm - 1
(3
). - The first
mid
is(1 + 3) / 2 = 2
. There is a black pixel at row2
. - Hence, we shift
left
tomid
, which is2
. - No more movement is possible, and
left
andright
converge to row2
which is our bottom edge.
Left Edge
- To find the left edge, we start with
left
at0
andright
aty
(2
). - The first
mid
is between column0
and2
, so it is1
. - Since column
1
has a black pixel, we moveright
tomid
, which is1
. - The next
mid
is(0 + 1) / 2 = 0
, but column0
has no black pixels so we moveleft
tomid + 1
which is1
. left
andright
converge at1
, so our left edge is column1
.
Right Edge
- We search for the right edge with
left
aty
(2
) andright
atn - 1
(4
). - The initial
mid
is(2 + 4) / 2 = 3
. - Even though column
3
has no black pixels, we don't moveleft
because it already has the correct value (y
), we moveright
tomid - 1
, which is2
. left
andright
converge at2
, defining our right edge which is column2
.
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.
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
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
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 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 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.