Number of Islands - Video Solutions

Problem Overview: You get a 2D grid of characters where '1' represents land and '0' represents water. An island is formed by connecting adjacent land cells horizontally or vertically. The task is to count how many separate islands exist in the grid.

Approach 1: Depth‑First Search (DFS) Flood Fill (Time: O(m×n), Space: O(m×n))

The core idea is to treat the grid like a graph where every land cell connects to its four neighbors. Iterate through the grid. When you encounter a '1', you discovered a new island. Start a DFS from that cell and recursively visit all connected land cells. During traversal, mark each visited cell as water or track it in a visited structure so it is not counted again.

This works because a DFS flood fill completely explores one connected component before moving on. Each cell is visited once, so the total runtime stays linear relative to the grid size. The recursion stack can grow up to O(m×n) in the worst case when the island covers the entire grid. This approach relies on standard graph traversal techniques used in Depth-First Search and grid traversal problems.

Approach 2: Breadth‑First Search (BFS) Traversal (Time: O(m×n), Space: O(m×n))

BFS solves the same connected‑component problem using a queue instead of recursion. Scan the grid until you find a land cell. Push it into a queue and repeatedly pop cells while exploring their four neighbors. Every time a neighboring cell contains '1', mark it visited and enqueue it.

The queue expands level by level across the island until all connected land is processed. Once the queue becomes empty, that island is fully explored and the outer grid scan continues. The algorithm still visits each cell at most once, giving O(m×n) time complexity. BFS is often preferred in languages where recursion depth could overflow the stack. This method highlights classic Breadth-First Search traversal on a matrix.

Approach 3: Union Find (Disjoint Set) (Time: O(m×n α(n)), Space: O(m×n))

Another perspective treats every land cell as a node in a disjoint‑set structure. Initially each land cell forms its own set. While scanning the grid, union the current cell with adjacent land neighbors. After processing the entire grid, the number of unique parent sets represents the number of islands.

This method uses path compression and union by rank for efficiency, giving near constant amortized operations. It’s particularly useful when connectivity relationships change dynamically, which is common in follow‑up variations. The structure is implemented with Union Find.

Recommended for interviews: DFS or BFS traversal is the expected answer. Both demonstrate that you recognize the grid as a connected‑component problem and can implement graph traversal efficiently. Starting with DFS is common because it is shorter to code, while BFS shows awareness of iterative alternatives when recursion depth might become an issue.