|
This post is completed by 2 users
|
Add to List |
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