Java DFS Solution and seeking for a binary search solution.


  • 15
    C

    DFS or BFS is the intuitive solution for this problem while the problem is with a tag "binary search". So can anyone provide a binary search answer. DFS complexity is O(m * n) and if binary search it would be O(n * lgm + m * lgn)

    public class Solution {
        private int minX = Integer.MAX_VALUE, minY = Integer.MAX_VALUE, maxX = 0, maxY = 0;
        public int minArea(char[][] image, int x, int y) {
            if(image == null || image.length == 0 || image[0].length == 0) return 0;
            dfs(image, x, y);
            return(maxX - minX + 1) * (maxY - minY + 1);
        }
        private void dfs(char[][] image, int x, int y){
            int m = image.length, n = image[0].length;
            if(x < 0 || y < 0 || x >= m || y >= n || image[x][y] == '0') return;
            image[x][y] = '0';
            minX = Math.min(minX, x);
            maxX = Math.max(maxX, x);
            minY = Math.min(minY, y);
            maxY = Math.max(maxY, y);
            dfs(image, x + 1, y);
            dfs(image, x - 1, y);
            dfs(image, x, y - 1);
            dfs(image, x, y + 1);
        }
        
    }

  • 1

    Binary search solution here


  • 0
    C

    I've just seen it. Very brilliant solution! Thank you Peisi!


  • 0

    Haha. Originally I thought "No way binary search. The black pixels can be a maze. It must be a wrong tag~"


  • 0
    C

    Me too and I thought about binary search in each row/col but found it doesn't work. Nice thought about projection! Binary search for the col/row that has black!!Really amazing.


  • 0
    C

    I also like the way you use the final position k to indicate whether it is a col/row that has black


  • 0

    I like your DFS solution. Tried it out on my computer. But I think you should put the initialization of the minX, minY, maxX, maxY inside the minArea otherwise if the OJ or anyone use one instance to calculate different cases the answer will be wrong.


Log in to reply
 

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