A complete summary of Java Solutions, BFS, DFS, and Union-Find with detailed explanation.


  • 0
    Y

    DFS with and without extra space

    public class Solution {
        /**
         * When input cannot be changed
         * 3 step algorithm:
         * 1. find an entrance of an island
         * 2. marked the islands using DFS
         * 3. counting the number of entrance
         * As is common in graph questions, we need to mark the nodes we have already visited. Since we cannot manipulate the input, we need extra space to store them. A boolean array is used in this question. 
         * So in each recursion, we only consider nodes whose visited value is false. 
         * O(n ^ 2) time, O(n ^ 2) space without consider the recursion stack.
         * The recursion stack would be O(n ^ 2) in the worse case. 
         * n ^ 2 is the size of grid. 
         */
        public int numIslands(char[][] grid) {
            if (grid == null) return 0;
            if (grid.length == 0 || grid[0].length == 0) return 0;
            
            int count = 0;
            int row = grid.length;
            int col = grid[0].length;
            boolean[][] visited = new boolean[grid.length][grid[0].length];
            for (int i = 0; i < row; i++) { 
                for (int j = 0; j < col; j++) { 
                    //find the entrance
                    //Traversing graph is always related to find the entrance
                    if (grid[i][j] == '1' && visited[i][j] == false) {
                        visited[i][j] = true;
                        count++;
                        DFS(grid, i, j, visited, row, col);
                    }
                }
            }
            
            return count;
        }
        
        private void DFS(char[][] grid, int x, int y, boolean[][] visited, int row, int col) {
            for (int i = -1; i <= 1; i++) {
                for (int j = -1; j <= 1; j++) {
                    //Search 4 direction from current point and mark them as visited. 
                    if (isValid(i, j, x, y, row, col) && grid[x + i][y + j] == '1' && visited[x + i][y + j] == false) {
                        visited[x + i][y + j] = true;
                        DFS(grid, x + i, y + j, visited, row, col);
                    }
                }
            }
        }
        
        /**
         * Boundary check. 
         * Since we only want to check 4 direction (vertical and horizontal), we need to make sure di and dj won't be 1 or 0 at the same time. 
         */
        private boolean isValid(int di, int dj, int x, int y, int row, int col) {
            return (Math.abs(di) != Math.abs(dj) && x + di >= 0 && x + di < row && y + dj >= 0 && y + dj < col);
        }
        
        /**
         * If we can change the input, we can mark visited points in place without using the extra boolean array.
         * We marded every '1' point we have visited as '0' and thus marked it. 
         * O(n ^ 2) time and O(1) space without considering the recursion stack
         * The recursion stack would be O(n ^ 2) in the worse case. 
         */
        public int numIslands(char[][] grid) {
            if (grid == null) return 0;
            if (grid.length == 0 || grid[0].length == 0) return 0;
            
            int count = 0;
            int row = grid.length;
            int col = grid[0].length;
            
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    if (grid[i][j] == '1') {
                        count++;
                        removeIslands(grid, i, j, row, col);
                    }
                }
            }
            
            return count;
        }
        
        private void removeIslands(char[][] grid, int x, int y, int row, int col) {
            grid[x][y] = '0';
            
            for (int i = -1; i <= 1; i++) {
                for (int j = -1; j <= 1; j++) {
                    if (isValid(i, j, x, y, row, col) && grid[x + i][y + j] == '1') {
                        removeIslands(grid, x + i, y + j, row, col);
                    }
                }
            }
        }
        
        private boolean isValid(int di, int dj, int x, int y, int row, int col) {
            return (Math.abs(di) != Math.abs(dj) && x + di >= 0 && x + di < row && y + dj >= 0 && y + dj < col);
        }
    }
    

    BFS

    public class Solution {
        /**
         * BFS method
         * Solve 2-dimension problem with 1-dimension index. index = i * n + j
         * Using a Queue
         * O(n ^ 2) time, O(n ^ 2) space in the worse case.
         */
        
        public int numIslands(char[][] grid) {
             if (grid == null) return 0;
             if (grid.length == 0 || grid[0].length == 0) return 0;
             
             int count = 0;
             int row = grid.length, col = grid[0].length;
             for (int i = 0; i < row; i++) {
                 for (int j = 0; j < col; j++) {
                     if (grid[i][j] == '1') {
                         removeIslands(grid, i, j, row, col);
                         count++;
                     }
                 }
             }
             
             return count;
        }
        
        private void removeIslands(char[][] grid, int x, int y, int row, int col) {
            grid[x][y] = '0';
            Queue<Integer> queue = new LinkedList<>();
            queue.add(x * col + y);
            while (!queue.isEmpty()) {
                int cur = queue.poll();
                int curX = cur / col;
                int curY = cur % col;
                
                for (int i = -1; i <= 1; i++) {
                    for (int j = -1; j <=1; j++) {
                        if (isValid(i, j, curX, curY, row, col) && grid[curX + i][curY + j] == '1') {
                            queue.add((curX + i) * col + curY + j);
                            grid[curX + i][curY + j] = '0';
                        }
                    }
                }
            }
        }
        
        private boolean isValid(int di, int dj, int x, int y, int row, int col) {
            return (Math.abs(di) != Math.abs(dj) && x + di >= 0 && x + di < row && y + dj >= 0 && y + dj < col);
        }
    }
    

    Union-Find

    public class Solution {
        /**
         * Union Find
         * O(n ^ 2) time, O(n ^ 2) space
         */
        public int numIslands(char[][] grid) {
            if (grid == null) return 0;
            if (grid.length == 0 || grid[0].length == 0) return 0;
            
            int row = grid.length;
            int col = grid[0].length;
            int[] tag = new int[row * col];
            
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    tag[i * col + j] = grid[i][j] == '1' ? i * col + j : -1;
                }
            }
            
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    if (grid[i][j] == '0') {
                        continue;
                    }
                    if (j + 1 < col && grid[i][j + 1] == '1') { //union down
                        union(i, j, i, j + 1, tag, col);
                    }
                    if (i + 1 < row && grid[i + 1][j] == '1') { //union right
                        union(i, j, i + 1, j, tag, col);
                    }
                }
            }
            
            int count = 0;
            //count root whose tag is equal to itself
            for (int i = 0; i < row * col; i++) {
                if (tag[i] == i) {
                    count++;
                }
            }
            
            return count;
        }
        
        private void union(int i1, int j1, int i2, int j2, int[] tag, int col) {
            int index1 = i1 * col + j1;
            int index2 = i2 * col + j2;
            
            if (tag[index1] == tag[index2]) { //same root
                return;
            }
            
            //change the one with bigger tag
            if (tag[index1] < tag[index2]) { 
                if (tag[index2] != index2) {
                    find(index1, index2, tag);
                } else {
                    tag[index2] = tag[index1];
                }
            } else {
                if (tag[index1] != tag[index2]) {
                    find(index2, index1, tag);
                } else {
                    tag[index1] = tag[index2];
                }
            }
        }
        
        private void find(int smIndex, int bgIndex, int[] tag) {
            while (tag[bgIndex] != bgIndex) {
                //find previous root and chang its tag
                int tmp = tag[bgIndex];
                tag[bgIndex] = tag[smIndex];
                bgIndex =  tmp;
            }
            tag[bgIndex] = tag[smIndex];
        }
    }
    

Log in to reply
 

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