Number of Islands - Video Solutions

Problem Overview: You are given an m x n grid of characters where '1' represents land and '0' represents water. Islands are formed by connecting adjacent land cells horizontally or vertically. The task is to count how many distinct islands exist in the grid.

Approach 1: Depth-First Search (DFS) Traversal (Time: O(m*n), Space: O(m*n))

This problem reduces to counting connected components in a grid. Iterate through every cell of the matrix. When you encounter a land cell '1', you've discovered a new island. Run a DFS from that cell and recursively visit all connected land cells (up, down, left, right), marking them as visited by turning them into '0'. This prevents counting the same island again. Each cell is visited at most once, so the traversal takes linear time relative to the number of cells. DFS is simple to implement and works naturally with recursion when exploring neighbors in a depth-first search pattern.

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

BFS solves the same connected-component problem but explores the grid level by level using a queue. When a '1' is found, push it into a queue and repeatedly pop cells while adding all valid neighboring land cells. Mark each visited cell as water to avoid revisiting. BFS avoids recursion depth limits and is often preferred in languages where recursion stacks are shallow. The algorithm still scans every cell once, giving O(m*n) time complexity. This method directly uses breadth-first search on a matrix grid to flood-fill each island.

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

Union Find models each land cell as a node in a disjoint set. Iterate through the grid and union adjacent land cells so they belong to the same set. Initially, every land cell is its own component. When two neighboring land cells are discovered, perform a union operation to merge their sets. After processing the grid, the number of unique parents represents the number of islands. Path compression and union-by-rank keep operations nearly constant time. This method is useful when connectivity queries appear frequently and highlights how Union Find can track components efficiently.

Recommended for interviews: DFS or BFS traversal. Both clearly demonstrate understanding of grid traversal and connected components. DFS is typically the fastest to implement during interviews. BFS is equally valid and avoids recursion depth concerns. Union Find shows deeper algorithm knowledge but usually adds unnecessary complexity for this specific problem.