This post is completed by 2 users

  • 1
Add to List
Medium

408. Number of Islands

Objective: 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. Assume all four edges of the grid are all surrounded by water. Given such a grid, write an algorithm to find the number of islands in it.

Example 1:
Input:
11110
11010
11000
00000
No of Islands: 1

Example 2:
Input:
11000
11000
00100
00011
No of Islands: 3

Example 3:
Input:
11110
00010
00010
11110
No of Islands: 1

Approach:

Use Depth-First Search

If all the nodes in the grid are connected then after DFS all the nodes will be visited and there will be only one Island in the grid. If there are more islands in the grid we need to multiple DFS to visit them all. So Number of Islands will be equal to the number of DFS required to visit all isLands (1's)

Start the DFS from the node with value 1 and try all four directions (right, left, up and down) to find any connected 1's. Once DFS is completed, check if there is an unvisited node with value 1 exists in the given grid, if yes then start another DFS from that node. Keep counting no of DFS's, this will be our answer- Number of Islands.

We will solve using both recursive and non-recursive approach.

Output:

No of Islands: 1
No of Islands: 3

Output:

No of Islands: 1
No of Islands: 3

Source: Leetcode