The grid holds 1 for land and 0 for water. An island is land connected up, down, left or right. Count the islands.
DSA Animator › DSA Revision › Matrix › Number of Islands
Remember: new unvisited land means a new island, then flood fill it. Sinking visited land prevents double counting. The video solves Number of Islands (LeetCode 200, Medium) with the DFS Flood Fill pattern from the Matrix topic, and you can replay every step in the interactive Number of Islands animation.
The grid holds 1 for land and 0 for water. An island is land connected up, down, left or right. Count the islands.
This grid has 3 islands. A 2 by 2 block in the top left, a single cell in the middle, and two cells in the bottom right.
Counting land cells is not enough, because one island can have many cells. We need to recognise which cells belong together.
Scan the grid cell by cell. When you find land that has not been visited, that is a new island, so add 1. Then flood fill: use DFS to visit every connected land cell, and mark it as water so it is never counted again.
At row 0, column 0, we find land: island number 1. DFS spreads through all four cells of the top left block and sinks them. The scan continues, and finds new land at row 2, column 2: island number 2, a single cell. Next, new land at row 3, column 3: island number 3. DFS sinks it, together with its right neighbour. The scan finishes with 3 islands.
In code, loop over every cell. When a cell is land, add 1 and call DFS on it. DFS stops at the border or at water, otherwise it marks the cell and calls itself in all four directions. Every cell is visited a constant number of times, so it's O of m times n time.
Remember: new unvisited land means a new island, then flood fill it. Sinking visited land prevents double counting.