Simple and clean Java DFS solution - fast 4ms.


  • 0
    J

    Just extend the black region as possible with DFS, then calculate the area of the min rectangle.

    public class Solution {
    private int xmin, xmax;
    private int ymin, ymax;
    
    public int minArea(char[][] image, int x, int y) {
    	if (image.length == 0 || image[0].length == 0 || image[x][y] != '1')
    		return 0;
    	xmin = xmax = x;
    	ymin = ymax = y;
    	dfsHelper(image, x, y);
        return (xmax - xmin + 1) * (ymax - ymin + 1);
    }
    
    private void dfsHelper(char[][] image, int x, int y) {
    	if (x < 0 || x >= image.length || y < 0 || y >= image[0].length || image[x][y] != '1')
    		return;
    	if (image[x][y] == '1') {
    		image[x][y] = '*'; // "*" indicate visited position.
    		xmin = Math.min(xmin, x);
    		xmax = Math.max(xmax, x);
    		ymin = Math.min(ymin, y);
    		ymax = Math.max(ymax, y);
    	}
    	dfsHelper(image, x-1, y);
    	dfsHelper(image, x, y-1);
    	dfsHelper(image, x+1, y);
    	dfsHelper(image, x, y+1);
    	return;
    } }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.