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.