200.Number of Islands

1-DFS O(M*N)

class Solution {
    public int numIslands(char[][] grid) {
        int n = grid.length;
        if(n < 1)
            return 0;
        int m = grid[0].length;
        int[][] visited = new int[n][m];
        int cnt = 0;
        for(int i = 0 ; i < n; i++){
            for(int j = 0; j < m; j++){
                if(grid[i][j] == '1' && visited[i][j] == 0 ){
                    dfs(grid, visited, i, j);
                    cnt++; 
                }
            }
        }
        return cnt;

    }
    public void dfs(char[][] grid, int[][] visited, int i, int j){
        visited[i][j] = 1;
        if( i>0 && grid[i-1][j] == '1' &&visited[i-1][j] == 0){
            dfs(grid, visited, i-1, j);
        }
        if( (i+1) < grid.length  && grid[i+1][j] == '1' &&visited[i+1][j] == 0){
            dfs(grid, visited, i+1, j);
        }
        if( j > 0 && grid[i][j - 1] == '1' &&visited[i][j - 1] == 0){
            dfs(grid, visited, i, j - 1);
        }
        if( (j + 1) < grid[0].length && grid[i][j + 1] == '1' && visited[i][j + 1] == 0){
            dfs(grid, visited, i, j + 1);
        }
    }
}

2- BFS

3- Union Find