Find Number of Islands - The Coding Shala

Home >> Interview Questions >> Find number of Islands

Find Number of Islands

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.
Example 1:

Input:

11110

11010

11000

00000

Output: 1



Example 2:

Input:
11000
11000
00100
00011
Output: 3

Number of Islands Java Program

Method 1:
Using dfs.

An Island is started if there is 1 present and surrounded by water(0). we will count island if 1 available and make all the adjacent to zero(0) or sink adjacent island so we don't count them again. We can use dfs or bfs to check adjacent lands. The following code is using dfs.

Java Code: 

class Solution {
    public int numIslands(char[][] grid) {
        //check if null or no element
        if(grid == null || grid.length == 0) return 0;
        int numIsland = 0;
        //check for every element
        for(int i=0; i<grid.length; i++){
            for(int j=0; j<grid[i].length;j++){
                //if there is 1 then only it can make an island
                if(grid[i][j]=='1'){
                    //make all the adjcent island to zero or sink :P
                numIsland += dfs(grid, i, j);
                }
            }
        }
        return numIsland;
    }
    
    private int dfs(char[][] grid, int i, int j){ //check all the adjcent island
        if(i<0 || i>=grid.length || j<0 || j>=grid[i].length || grid[i][j]=='0'){
            return 0;
        }
        grid[i][j] = '0'; //sink all the island
        dfs(grid, i-1, j);
        dfs(grid, i+1, j);
        dfs(grid, i, j-1);
        dfs(grid, i, j+1);
        return 1;
    }
}
Method 2:
Using bfs.
We will bfs to visit the adjacent island.

Java Code: 

class Solution {
    //for storing purpose bfs
    Queue<int[]> queue = new LinkedList<>();
    
    public int numIslands(char[][] grid) {
        if(grid == null || grid.length==0) return 0;
        int numIsland = 0;
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j]=='1' && !visited[i][j]){
                    queue.offer(new int[]{i,j});
                    visited[i][j] = true;
                    bfs(grid, visited);
                    numIsland++;
                }
            }
        }
        return numIsland;
    }
    
    //bfs
    void bfs(char[][] grid, boolean[][] visited){
        int[][] direction = {{-1, 0}, {1,0}, {0,-1}, {0,1}};
        while(!queue.isEmpty()){
        int[] current = queue.poll();
        for(int[] dir : direction){
            int i = current[0]+dir[0];
            int j = current[1]+dir[1];
            
            if(i<0 || i>= grid.length || j<0 || j>= grid[i].length 
                   || visited[i][j] || grid[i][j]=='0'){
                continue;
            }
            visited[i][j] = true;
            queue.offer(new int[]{i,j});
         }
        }
    }
}

Here DFS is fast compared to the BFS.


Other Posts You May Like
Please leave a comment below if you like this post or found some error, it will help me to improve my content.

Comments

Popular Posts from this Blog

Anti Diagonals - The Coding Shala

Shell Script to find sum, product and average of given numbers - The Coding Shala

LeetCode - Bulb Switcher Solution - The Coding Shala

New Year Chaos Solution - The Coding Shala

Sorting the Sentence LeetCode Solution - The Coding Shala