Number of Islands LeetCode Solution: DFS, BFS & Union-Find

Number of Islands (#200) is one of the most frequently asked medium problems on LeetCode — and for good reason. The number of islands leetcode problem is the single best entry point into grid-based graph problems, a category that appears relentlessly in coding interviews at every major tech company.

The problem is elegant in its simplicity: given a 2D grid of characters where "1" represents land and "0" represents water, count the number of distinct islands. An island is a group of adjacent land cells connected horizontally or vertically, surrounded by water on all sides.

What makes this problem so valuable is not just the solution itself but the pattern it teaches. Once you understand how to traverse a grid and count connected components, you can solve dozens of related problems — from Rotting Oranges (#994) to Pacific Atlantic Water Flow (#417). This walkthrough covers three distinct approaches: DFS, BFS, and Union-Find.

The input is a 2D grid of characters — not integers. Each cell contains either "1" (land) or "0" (water). Your task is to return the total number of islands, where an island is defined as a group of connected "1" cells. Two cells are connected if they share an edge horizontally or vertically — diagonal connections do not count.

Consider a simple example: a 4x5 grid with two clusters of "1" cells separated by water. The first cluster in the top-left forms one island, and the second cluster in the bottom-right forms another, so the answer is 2. The key constraint is that connectivity is only through the four cardinal directions — up, down, left, right.

This is fundamentally a connected components problem on a graph. Each land cell is a node, and each pair of adjacent land cells shares an edge. Counting islands is equivalent to counting the number of connected components in this implicit graph. Once you see the grid as a graph, standard traversal algorithms apply directly.

The most intuitive approach to the number of islands leetcode problem is depth-first search. The algorithm is straightforward: iterate through every cell in the grid. When you find an unvisited "1", increment your island count and launch a DFS from that cell to mark all connected land cells as visited. Each DFS call explores one complete island.

The DFS function visits the current cell, marks it as visited (by changing "1" to "0" or using a visited set), and then recursively explores all four neighboring cells. The recursion naturally handles any island shape — L-shaped, U-shaped, or sprawling — because it follows every path until it hits water or the grid boundary.

The time complexity is O(m * n) where m and n are the grid dimensions, because every cell is visited at most once. The space complexity is also O(m * n) in the worst case due to the recursion stack — imagine a grid that is entirely land, where the DFS recursion depth equals the total number of cells.

In practice, the DFS approach is the cleanest and most common solution you will see in interviews. It takes about 10 lines of code and clearly demonstrates that you understand graph traversal on grids. Most interviewers expect this as the first solution.

The BFS approach follows the same high-level strategy as DFS — scan the grid, and for each unvisited land cell, explore the entire island. The difference is that BFS uses a queue instead of recursion, which makes it iterative and avoids potential stack overflow issues on very large grids.

When you find a "1", add its coordinates to a queue, mark it visited, and process the queue. For each cell you dequeue, check all four neighbors. If a neighbor is land and unvisited, mark it visited and enqueue it. When the queue empties, you have finished one island. Increment the counter and continue scanning.

The time and space complexity are both O(m * n), identical to DFS. However, the space usage pattern differs: BFS uses queue memory proportional to the width of the island being explored, while DFS uses stack memory proportional to the depth. For very large grids — say 1000x1000 or larger — the number of islands BFS approach is safer because it avoids deep recursion.

BFS is also the natural choice if an interviewer asks a follow-up like "find the shortest path between two cells" or "process cells level by level." Knowing both BFS and DFS for grid problems makes you flexible during interviews.

Union-Find (also called Disjoint Set Union) takes a fundamentally different approach. Instead of traversing islands one by one, you process all cells and union adjacent land cells into the same set. The final number of distinct sets equals the number of islands.

Initialize a Union-Find structure where each land cell is its own component. Then scan the grid: for each "1" cell, union it with its right and bottom neighbors if they are also "1" (you only need two directions because the other two are handled when those cells are processed). After processing all cells, count the number of distinct root parents among land cells.

The time complexity is nearly O(m * n) with path compression and union by rank — each union and find operation runs in amortized O(alpha(n)) time, where alpha is the inverse Ackermann function, effectively constant. Space is O(m * n) for the parent and rank arrays.

Union-Find is overkill for the basic island counting algorithm, but it teaches a pattern that is essential for harder problems. Problems like Accounts Merge (#721), Redundant Connection (#684), and Number of Connected Components (#323) all rely on Union-Find. Learning it here on a familiar problem makes those harder problems much more approachable.

Before submitting, consider the edge cases that trip up many candidates. An empty grid (0 rows or 0 columns) should return 0. A grid that is entirely water returns 0. A grid that is entirely land returns 1 — the entire grid is one island. A single-cell grid returns 1 if it is land, 0 if it is water.

A subtle edge case is modifying the input grid in-place versus using a separate visited structure. Changing "1" to "0" during DFS is a common trick that saves memory, but some interviewers may ask you not to modify the input. In that case, use a boolean visited matrix or a hash set of coordinates.

The number of islands problem is the foundation for a family of grid traversal leetcode problems. Once you master it, tackle these related problems in order: Max Area of Island (#695) — same DFS but track area per island. Surrounded Regions (#130) — mark regions NOT connected to the border. Number of Distinct Islands (#694) — track island shapes using relative coordinates. Rotting Oranges (#994) — multi-source BFS with a time dimension. Pacific Atlantic Water Flow (#417) — reverse BFS from both oceans.

The most important takeaway from the number of islands leetcode problem is this: a 2D grid IS a graph. Each cell is a node, and adjacency defines the edges. Once you internalize this mental model, every grid problem becomes a graph problem — and you already know how to solve graph problems with DFS, BFS, and Union-Find.

This pattern — scan the grid, traverse connected components, track state — appears in at least a dozen commonly asked interview problems. Surrounded Regions (#130), Pacific Atlantic Water Flow (#417), Walls and Gates (#286), and Shortest Path in Binary Matrix (#1091) all use the same fundamental approach with minor variations.

If you are preparing for coding interviews, make Number of Islands your first grid problem. Implement all three approaches — DFS for intuition, BFS for safety on large inputs, and Union-Find for the pattern it teaches. Then use YeetCode flashcards to drill the grid traversal pattern until recognizing it becomes second nature. The connected components grid pattern is one of the highest-value patterns you can master.