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

## Comments

## Post a Comment