This page explains Java solution to problem `Smallest Rectangle Enclosing Black Pixels`

using `Depth First Search`

algorithm.

An image is represented by a binary matrix with `0`

as a white pixel and `1`

as a black pixel. The black pixels are connected, i.e., there is only one black region. Pixels are connected horizontally and vertically. Given the location `(x, y)`

of one of the black pixels, return the area of the smallest (axis-aligned) rectangle that encloses all black pixels.

Input:

[

"0010",

"0110",

"0100"

]

x = 0, y = 2Output: 6

```
package com.vc.hard;
class SmallestRectangleEnclosingBlackPixels {
private int top, bottom, left, right = 0;
public int minArea(char[][] image, int x, int y) {
if(image == null || image.length == 0) return 0;
top = image.length - 1;
bottom = 0;
left = image[0].length - 1;
right = 0;
helper(image, x, y);
return (right - left + 1) * (bottom - top + 1);
}
private int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
private void helper(char[][] image, int x, int y) {
if(image[x][y] == 0) return;
image[x][y] = 0;
top = Math.min(x, top);
bottom = Math.max(bottom, x);
left = Math.min(left, y);
right = Math.max(right, y);
for(int[] dir: dirs) {
int xNew = x + dir[0];
int yNew = y + dir[1];
if(xNew >= 0 && xNew < image.length && yNew >= 0 && yNew < image[0].length
&& image[xNew][yNew] == '1') {
helper(image, xNew, yNew);
}
}
}
}
```

O(M * N) Where

M is total number of rows in an input array

N is total number of cols in an inupt array

O(1)