Finding Number of Islands is a common problem in computer science, where the task is to determine the number of distinct islands in a 2-dimensional grid. In this problem, the grid is represented as a 2D matrix, where each cell can have a value of either 0 or 1. Value of 1 represents land, and a 0 represents water. An island is defined as a group or cluster of connected land cells (represented by 1s) in the 2D matrix. These land cells are considered connected if they are adjacent to each other horizontally or vertically, but not diagonally.
For example, consider the below graph/map:
1 1 0 0 0
1 1 0 0 0
0 0 0 0 0
0 0 0 1 1
In this matrix, there are two islands:
- Island 1: The four
1s in the top-left corner - Island 2: The two
1s in the bottom-right corner
Let’s consider another sample graph/map:
1 1 0 1 0
1 0 0 0 0
0 0 1 0 1
0 0 0 0 1
This matrix contains four islands:
- Island 1: The three
1s in the top-left corner - Island 2: The single
1near the top-right corner - Island 3: The single
1near the middle - Island 4: The two
1s near the bottom right corner
Let’s consider one other example graph/map:
1 1 0
0 0 1
0 0 1
This matrix contains two islands:
- Island 1: The two
1s in the top-left corner - Island 2: The two
1s in the bottom-right corner. Even though the two1s near the top right of the grid seem to be diagonally close, they can’t be considered and connected. Only horizontal or vertical connections are considered to be connected.
In order to solve this problem programmatically, we need to think of the 2D matrix as a graph, where each cell is a node, and the cells that are adjacent (up, down, left, right) are considered connected. There are two common approaches to solving this problem: Depth-First Search (DFS) and Breadth-First Search (BFS).
Depth First Search Approach
Below the implementation of a depth-first search (DFS) algorithm to find the number of islands in a 2D grid:
In the above implementation, we modified the input grid and changed the value from 1 to 0 after we visited each land cell. If you do not wish to change the input, you can use a visited and add/check visited co-ordinates (row, column) to this set. BFS implementation given below contains hints on how you can do this.
Breadth First Search Approach
Below the implementation of a Breadth-first search (BFS) algorithm to find the number of islands in a 2D grid:
If you are allowed to change the grid, you can also set all visited island cells to 0 like we did in DFS approach.
Time & Space Complexity
Both the DFS and BFS approaches have a time complexity of O(m*n), where m and n are the dimensions of the 2D matrix, as we need to visit each cell at least once. The space complexity for the DFS approach is O(m*n) in the worst case (If we consider the extra space used to store visited information. If the grid can be modified, this can be ignored).