Member-only story
Solving Graph Problems — Number of Islands
Let’s solve the famous Number of Islands Problem and its various similar problems.
Hello everyone! I have now started writing articles related to some Data Structures and Algorithms, and I would be doing it topic wise. I have chosen to begin with Graphs since it is an important topic. This article will not be the only one in Graph related problems. I will be writing some more articles attributed to Graph coding problems, and this one is the first of them.
In the complete Graph series, I aim to cover all the significant algorithms related to graph coding problems which are:-
- Breadth-First Search (BFS)
- Depth-First Search (DFS)
- Disjoint Set — Union Find
- Dijkstra’s Algorithm
So, in the first part, we would deal with all the Island counting related problems. I will be linking the problems with their Leetcode pages so that you can go and practice them there.
I will explain the problem and the solution approach and would also provide working code in C++ language.
1. Number of Islands
Problem Statement
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1Explanation: As we can see, all the 1’s are connected either horizontally or vertically, so have only a single island group.
Example 2:
Input: grid = [
["1","0","0","0","0"],
["1","0","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3Explanation: Here, we have 3 island groups. One formed by the 1’s at indices (0,0) and (1,0). The Second is formed by a single 1 present at (2,2). The third one is formed…
