### 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

public int numIslands(char[][] grid) {
if(grid == null || grid.length==0) return 0;
int numIsland = 0;
int m = grid.length;
int n = grid.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+dir;
int j = current+dir;

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