L200 Numbers of Island

DFS

Problem

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Input:
11110
11010
11000
00000

Output: 1

• An island is connected by adjacent lands('1') horizontally or vertically, so we need to find all adjacent '1's.

• Use dfs to consider this problem, bcz dfs could traverse from the beginning to the end. We could use dfs for searching four different orientations.

TC : O(mn) SC: O(1), if we need to consider the char, then O(mn)

why TC is O(mn): flag '0' at each 1's, so then we will not return to the area we already visited.

L200 nums of island

 public int numIslands(char[][] grid) {
        if(grid == null || grid.length == 0) return 0;
        int row = grid.length;
        int col = grid[0].length;
        int count = 0;
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(grid[i][j] == '1'){
                   dfs(grid, i, j);
                   count++; 
                }
                
            }
        }
        return count;
    }
    private void dfs(char[][] grid, int i, int j){
        if(i < 0 || j < 0 ||i >= grid.length || j >= grid[0].length || grid[i][j] != '1') return;
        grid[i][j] = '0';
        dfs(grid, i+1, j);
        dfs(grid, i-1, j);
        dfs(grid, i, j+1);
        dfs(grid, i, j-1);
        
    }

Where should be noticed?

• 8 --> if(grid[i][j] == '1') without this, all of the index value gonna be added together.

• 18 --> corner case i < 0 || j < 0, without this, out of bonds, eg: what if i -1 < 0?