Number of Islands is a classic graph problem that often appears in interviews. More importantly though, understanding the solution to this question is vital as it is foundational in solving more complex challenges. In particular, we’ll explore how to use the Depth-First Search algorithm.
1. Visualizing the Problem
An island, in the context of this problem, is defined as a horizontally or vertically contiguous group of cells with a value of 1 that are surrounded by water cells with a value of 0.
The m x n 2D binary grid serves as a map, illustrating where land and water cells are located. It’s crucial to note that any cell that extends beyond this grid is considered water, and an island must be surrounded by water.
In this case we can clearly see that the map provided contains a single large island. It is a single island because all of the island cells are connected to each other, and the group as a whole is surrounded by water on all sides.
