# Easy to understand O(n^2) time O(n^2) space solution using DFS

• ``````public class Solution {
/*
This problem is similar to counting number of connected components in graph and can be
solved using dfs approach.
*/
int count = 0;
public int numIslands(char[][] grid) {
int m = grid.length;
if(m==0) return 0;
int n = grid[0].length;

boolean [][]visited = new boolean[m][n]; //maintaining a visited array to mark all elements we have already visited

for(int i = 0;i<m;i++){
for(int j = 0;j<n;j++){
if(isSafe(grid, visited, i,j)){
dfs(grid, visited, i,j);
++count;
}

}
}

return count;
}

public boolean isSafe(char[][]grid,boolean[][]visited, int startRow, int startCol){
int m = grid.length;
int n = grid[0].length;

return ( startRow>=0 && startRow < m && startCol >=0 && startCol < n && grid[startRow][startCol] == '1' && !visited[startRow][startCol] );
}

public void dfs(char[][]grid, boolean[][]visited, int startRow, int startCol){
visited[startRow][startCol] = true;

if( isSafe(grid, visited, startRow-1, startCol) ) {

dfs(grid, visited, startRow-1, startCol);
}
if( isSafe(grid, visited, startRow+1, startCol) ) {

dfs(grid,visited, startRow+1, startCol);
}

if( isSafe(grid, visited, startRow, startCol-1) ){

dfs(grid, visited, startRow, startCol-1);
}

if( isSafe(grid, visited, startRow, startCol+1) ) {

dfs(grid, visited, startRow, startCol+1);
}

}
}``````

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