Find the total number of islands using DFS | Faceprep

Find the total number of islands using DFS | Faceprep

The program to find the total number of islands using DFS is discussed here. Given an input island matrix, where 0 represents water and 1 represents land. Find the total number of islands that are formed by connected 1’s.


find the total number of islands using dfs algorithm


For example, consider the input island matrix

1 0 1 0 1

0 0 1 0 0

0 0 1 1 0

0 1 0 1 0

1 1 1 0 0

0 0 0 0 1

0 1 0 1 0

0 0 1 1 0

0 0 0 1 1

1 1 0 0 0


Total number of islands = 5

number of islands using dfs algorithm


Algorithm to find the number of islands using DFS

  1. Input the island matrix.
  2. Traverse the entire matrix.
  3. Whenever you find 1 use DFS to find all the connected ones in the 8 direction.
  4. Change them to 0 to indicate that this element is traversed and increase the island count by 1.
  5. Return count.

The program to find the number of islands using DFS is given below.

@@coding::1@@

Time complexity: O(n^2)


find the total number of islands using dfsClick here to learn more about FACE Prep PRO



Recommended Programs



number of islands

c