JAVA DFS readable solution: Time O(nm) extra space for visited[][] matrix


  • 0
    C

    [Analysis]
    The overall idea is to DFS the 4 directions for every point.
    There are basically four cases when visiting a point grid[i][j]

    1. This is a '1' and it has not yet been visited.

    2. This is a '0'

    3. It s '1' but the other part of this island has been visited.

    4. grid[i][j] is outside the board.

    2), 3), 4) basically mean the same thing, that you cannot count one more island by getting these result.
    On the opposite, once you get 1), do islandcount++

    Time Complexity is O(nm) because you only do calculation on a grid once and return false immediately if it lies in 2),3),4).
    An extra matrix boolean visited[][] is needed to identify the islands to prevent counting the same island multiple times, therefore the space is O(nm)

    [Code]

    public class Solution {
        int islandNum = 0;
        public int numIslands(char[][] grid) {
            if(grid == null || grid.length == 0 || grid[0].length == 0)
                return 0;
            int row = grid.length;
            int col = grid[0].length;
            boolean[][] visited = new boolean[row][col];
            for(int i = 0; i < grid.length; i++) {
                for(int j = 0; j < grid[0].length; j++) {
                    boolean foundIsland = numIslands(grid, visited, i, j);
                    if(foundIsland)
                        islandNum++;
                }
            }
            return islandNum;
        } 
        public boolean numIslands(char[][] grid, boolean[][] visited, int i, int j) {
            /*
              stop visiting if 
              1.outside the board
              2.already visited
              3.is water
            */
            if(i < 0 || grid.length <= i || j < 0 || grid[0].length <= j 
               || visited[i][j] == true 
               || grid[i][j] == '0')
                return false;
            visited[i][j] = true;
            //expend to identify the whole island on the visited matrix
            numIslands(grid, visited, i - 1, j);
            numIslands(grid, visited, i + 1, j);
            numIslands(grid, visited, i, j - 1);
            numIslands(grid, visited, i, j + 1);
            return true;
        }
    }

Log in to reply
 

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