# Smallest Rectangle Enclosing Black Pixel

This page explains Java solution to problem `Smallest Rectangle Enclosing Black Pixels` using `Depth First Search` algorithm.

## Problem Statement

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.

Example 1:

Input:
[
"0010",
"0110",
"0100"
]
x = 0, y = 2
Output: 6

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
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);
}
}
}
}
``````

## Time Complexity

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)