Short Java Solution (13 ms)


  • 0
    C

    Explanation

    Run DFS from given point (x,y) and along the way update the extremes of the rectangle with min/max.

    public int minArea(char[][] image, int x, int y) {
        if(image == null || image.length == 0) return 0;
        int[] rect = new int[] {x, x,y,y};
        dfs(image, new boolean[image.length][image[0].length], x,y,rect);
        System.out.println(Arrays.toString(rect));
        return (rect[1]-rect[0]+1)*(rect[3]-rect[2]+1);
    }
    
    public void dfs(char[][] image, boolean[][] visited, int x, int y, int[] rect){
        visited[x][y] = true;
        rect[0] = Math.min(rect[0], x);
        rect[1] = Math.max(rect[1], x);
        rect[2] = Math.min(rect[2], y);
        rect[3] = Math.max(rect[3], y);
        int[] rows = {-1,0,0,1};
        int[] cols = {0,-1,1,0};
        for(int k=0; k < 4; k++){
            int i = x+ rows[k];
            int j = y+ cols[k];
            if(i >=0 && i < image.length && j >= 0 && j < image[0].length && !visited[i][j] && image[i][j] == '1'){
                dfs(image, visited, i, j, rect);
            }
        }
    }

  • 0
    C

    Oops. Included the print statement in my code by accident. Should be <13 ms then :)


Log in to reply
 

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