Leetcode: Smallest Rectangle Enclosing Black Pixels

 This question is asked at Google. It is as follows: 

You are given an mxn binary matrix where 0 represents a white pixel and 1 represents a black pixel, and the black pixels are connected, both horizontally and vertically (a cross). Given 2 integers, return the area of the smallest rectangle. Write in O(mn) complexity. 

Here are the examples: 

Input: image = [["0","0","1","0"],["0","1","1","0"],["0","1","0","0"]], x = 0, y = 2

Output: 6

Input: image = [["1"]], x = 0, y = 0

Output: 1

Now the intuition between this is to do Depth First Search/Breadth First Search. We can try to do an exhaustive search. 

So we have a method with the starting point and the image, which is basically the same area of the graph. Base case is we return 0 if the length of the array is 0 (there are no black pixels then.) We return either the difference between the min/max point of x and y.

In the minArea function, we set the top, bottom, left, right, to the corresponding point indicated so we can check for edges, then call Depth-First search and return the resulting rectangles. The depth first search maniplates the left and right points based on the children. We return in DFS if we have reached an edge otherwise we remove the pixel as WHITE (genius right?). Then we run DFS in all of the directions. We just go over all edges until everything has been reached (childrenwise recursively) and then just update the min and max x and y values. 

Here's the code: 

public class Solution {

    private int top, bottom, left, right;

    public int minArea(char[][] image, int x, int y) {

        if(image.length == 0 || image[0].length == 0) return 0;

        top = bottom = x;

        left = right = y;

        dfs(image, x, y);

        return (right - left) * (bottom - top);

    }

    private void dfs(char[][] image, int x, int y){

        if(x < 0 || y < 0 || x >= image.length || y >= image[0].length ||

          image[x][y] == '0')

            return;

        image[x][y] = '0'; // mark visited black pixel as white

        top = Math.min(top, x);

        bottom = Math.max(bottom, x + 1);

        left = Math.min(left, y);

        right = Math.max(right, y + 1);

        dfs(image, x + 1, y);

        dfs(image, x - 1, y);

        dfs(image, x, y - 1);

        dfs(image, x, y + 1);

    }

}