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


  • 0
    T
    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);
           }
           
       }
    }

Log in to reply
 

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