Finding the total number of islands is one of the most asked interview questions till date. A product-based company like Adobe and Infosys frequently asked this question as a part of their technical interview. As the number of island problems includes the concept and application of data structures and graphs, it helps the interviewer test the candidate's understanding for the same.
Problem: Find the Number of Islands
You are given a matrix “mat” with dimensions m*n, which represents a map of “1’s” as a land of the island and “0’s” as the water around the island. Island is surrounded by the water and connects adjacent lands horizontally and vertically, as shown in the figure below. Find out the total number of islands.
Before we start coding the problem's solution, let us first understand the problem description and working of the problem to find the solution.
Looking at the above problem description, the "Number of island" problem is a variable of the standard problem “Find the number of connected components in an undirected graph.” As you know, a graph is a group of nodes and edges that are used to connect these nodes. Therefore, the connected component of an undirected graph is a subgraph where every two nodes are connected by a path(s). The below image shows the connected components of the graph.
The given problem can be solved easily using Depth First Search Algorithm(DFS) on each component. Depth First Search Algorithm is a recursive algorithm that uses backtracking to search all the nodes of the graph by going ahead if the potential node is found, else use the backtracking approach. When DFS is called, a component of the undirect graph is visited. After the complete iteration, we will call DFS again on the next un-visited component. Therefore, the number of calls of DFS gives the total number of connected components of the graph.
Now comparing the connected components of an undirected graph with the "Number of island" problem, the node of the graph will be the “1’s” (land) in the matrix. We will call the depth-first search algorithm on the ‘1's’ of the matrix. Later during the DFS call, every visited cell of the matrix is set as ‘0’ to mark it as a visited node. At last, count the number of total DFS calls, which indicates the total number of islands since each DFS call starts when a new island is identified.
Let's take a look at the example below for a better understanding.
Consider a matrix “mat” of size 3x3 i.e. m=n=3. The “1’s” in the matrix represent the island's land area, and the “0’s” represent the water around the island.
Now, we will call the DFS algorithm from the first cell, i.e., mat of the matrix. The algorithm will traverse all the matrix cells containing “1’s” by using the recursive backtracking method, as shown below in the highlighted area.
After each visit of the cell containing “1’s”, we will replace it with “0” to mark the cell as visited and avoid the repetition of the algorithm.
Later again, we call the DFS algorithm on the other matrix cell containing “1” but not visited previously. The process keeps repeating until all the cells of the matrix are zero.
To find out the total number of islands as the final output of the problem, we will count the number of DFS calls throughout the problem. Therefore, for the given matrix, the number of islands is 2.
The running time complexity for finding the number of islands for the given matrix is O(m*n), where m and n are rows and columns, respectively.
The space complexity of the problem is O(min(m,n)) as in the worst case where the matrix is filled with lands, and the size of the queue can grow up to min(m,n).