Leetcode 302. Smallest Rectangle Enclosing Black Pixels
Problem
Given an n x m
binary matrix representing an image where 0
means a white pixel and 1
represents a black pixel. All the 1s
(black pixels) are connected and forms a single connected region. Two pixels are connected if they are adjacent vertically or horizontally. Our task is to find the area of the smallest rectangle that can enclose all of the black pixels. For this, we are given the location of one of the black pixels in (x, y)
coordinates.
For example:
If the image is represented as:
1 2 3[ 4 "0010", 5 "0110", 6 "0100" 7]
and x = 0, y = 2, The area of the smallest rectangle that can enclose all black pixels is 6.
Approach:
The given problem can be solved by using Breadth-First-Search approach along with the Queue data structure.
As we are given the coordinates of a black pixel, we first add it to the queue and mark it as visited in the image. After that for each pixel in the queue, we look for its neighboring pixels in all four directions(top, bottom, right and left). If any of its neighbor is a black pixel and not visited, we add it to the queue and mark it as visited. Further, we update the top-left and bottom-right coordinates of the rectangle based on the current pixel.
We repeat this approach until all the black pixels are visited and queue becomes empty. The resultant rectangle formed by the top-left and bottom-right coordinates encloses all the black pixels and is the smallest possible. The area of this rectangle is calculated by multiplying its width and height.
Python Solution:
1 2python 3from collections import deque 4class Solution: 5 def minArea(self, image: List[List[str]], x: int, y: int) -> int: 6 m, n, topLeft, bottomRight = len(image), len(image[0]), [x, y], [x, y] 7 q = deque([(x, y)]) 8 image[x][y] = "2" # mark as visited 9 dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)] # up, down, left, right 10 while q: 11 x, y = q.popleft() 12 for dx, dy in dirs: 13 nx, ny = x + dx, y + dy 14 if 0 <= nx < m and 0 <= ny < n and image[nx][ny] == "1": 15 q.append((nx, ny)) 16 image[nx][ny] = "2" # mark as visited 17 topLeft = [min(topLeft[0], nx), min(topLeft[1], ny)] 18 bottomRight = [max(bottomRight[0], nx), max(bottomRight[1], ny)] 19 return (bottomRight[1] - topLeft[1] + 1) * (bottomRight[0] - topLeft[0] + 1)
Java Solution:
1
2java
3class Solution {
4 public int minArea(char[][] image, int x, int y) {
5 int m = image.length, n = image[0].length;
6 int[] topLeft = new int[]{x, y}, bottomRight = new int[]{x, y};
7 Queue<int[]> q = new LinkedList<>();
8 q.offer(new int[]{x, y});
9 image[x][y] = '2'; // mark as visited
10 int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // up, down, left, right
11 while (!q.isEmpty()) {
12 int[] cur = q.poll();
13 for (int[] dir : dirs) {
14 int nx = cur[0] + dir[0], ny = cur[1] + dir[1];
15 if (nx >= 0 && nx < m && ny >= 0 && ny < n && image[nx][ny] == '1') {
16 q.offer(new int[]{nx, ny});
17 image[nx][ny] = '2'; // mark as visited
18 topLeft[0] = Math.min(topLeft[0], nx);
19 topLeft[1] = Math.min(topLeft[1], ny);
20 bottomRight[0] = Math.max(bottomRight[0], nx);
21 bottomRight[1] = Math.max(bottomRight[1], ny);
22 }
23 }
24 }
25 return (bottomRight[0] - topLeft[0] + 1) * (bottomRight[1] - topLeft[1] + 1);
26 }
27}
JavaScript Solution:
1 2javascript 3var minArea = function(image, x, y) { 4 var m = image.length, n = image[0].length; 5 var topLeft = [x, y], bottomRight = [x, y]; 6 var q = [[x, y]]; 7 image[x][y] = '2'; // mark as visited 8 var dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]; // up, down, left, right 9 while (q.length > 0) { 10 var cur = q.shift(); 11 for (var dir of dirs) { 12 var nx = cur[0] + dir[0], ny = cur[1] + dir[1]; 13 if (nx >= 0 && nx < m && ny >= 0 && ny < n && image[nx][ny] == '1') { 14 q.push([nx, ny]); 15 image[nx][ny] = '2'; // mark as visited 16 topLeft[0] = Math.min(topLeft[0], nx); 17 topLeft[1] = Math.min(topLeft[1], ny); 18 bottomRight[0] = Math.max(bottomRight[0], nx); 19 bottomRight[1] = Math.max(bottomRight[1], ny); 20 } 21 } 22 } 23 return (bottomRight[0] - topLeft[0] + 1) * (bottomRight[1] - topLeft[1] + 1); 24};
This solution works by doing a Breadth First Search to explore all the black pixels. It starts from one of the black pixels mentioned in the problem input. For each black pixel discovered, the solution maintains top-left and bottom-right coordinates which would bound all discovered black pixels.
It uses '0', '1' and '2' to identify white, unvisited black, and visited black pixels respectively. If the BFS can discover a black pixel in any of the four directions surrounding the current pixel, it feeds it back to the Queue so that the neighboring black pixels to that one could also be traced in subsequent iterations.
Finally, when all unvisited black pixels are discovered and marked visited, the rectangle encapsulating all the black cells can be determined using top-left and bottom-right masks. And, the area of such rectangular region is computed using width and height bounded by top-left and bottom-right of the rectangle.
The same logic was implemented for Python, Java and JavaScript. However, for the sake of languages' syntax, some of the data structures used in the solution change. Python makes use of deque
for creating queue with methods popleft
and append
, in Java LinkedList
is used and poll
and offer
methods are used, while shift
and push
methods were used for the queue implementation with JavaScript.
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.