Number of Islands LeetCode 200 Deep Dive

LeetCode 200 — Number of Islands — gives you an m x n 2D binary grid composed of characters '1' (land) and '0' (water). Your task is to count the number of islands. An island is a group of land cells connected horizontally or vertically, surrounded entirely by water or the grid boundary. The grid is guaranteed to be rectangular.

The problem is the canonical example of counting connected components in a grid. Every approach — DFS, BFS, or Union-Find — reduces to the same core idea: find an unvisited land cell, mark its entire connected component as visited, and increment the island count. The choice of traversal method determines code length, space usage, and suitability for follow-up variants.

Number of Islands appears in nearly every graph and grid interview. It is the gateway problem to a family of grid connectivity challenges including Surrounded Regions, Pacific Atlantic Water Flow, Number of Islands II, and Rotting Oranges. Mastering the flood fill pattern here unlocks all of them.

The DFS flood fill approach iterates every cell in the grid. When a land cell ('1') is encountered, the island count is incremented and a DFS is launched from that cell to sink the entire connected island — marking all reachable '1' cells as '0'. After the DFS completes, the island has been eliminated from further consideration.

This is called flood fill because the DFS floods outward from the starting cell in all four directions, converting land to water as it goes. Each subsequent outer loop iteration that encounters a '0' simply skips it. The count increments exactly once per island, because by the time the outer loop reaches any other cell of that island it has already been converted to '0'.

The flood fill pattern is elegant because it requires no external data structure for visited tracking. The grid itself serves as the visited set: a '0' means either original water or already-visited land. Sinking visited cells to '0' is an in-place modification that runs in O(1) extra space per cell.

The outer loop runs over all (i, j) pairs. When grid[i][j] == '1' is found, the island count is incremented and dfs(i, j) is called. The DFS function immediately marks grid[i][j] = '0' to prevent revisiting, then recursively calls itself on the four neighbors. Base cases: return immediately if i or j is out of bounds, or if grid[i][j] == '0'.

The recursion order (up, down, left, right) does not matter — DFS will explore the entire connected component regardless of direction order. Stack depth equals the longest path reachable from the starting cell, which in the worst case is O(m * n) for a snake-shaped island that fills the entire grid. Python's default recursion limit (1000) can be hit on very large grids; set sys.setrecursionlimit appropriately or switch to BFS.

Time complexity: O(m * n) — every cell is visited at most once by the outer loop and once by a DFS call. Space complexity: O(m * n) in the worst case for the DFS call stack (a fully connected island). In practice the stack depth is the size of the largest island.

The BFS alternative uses the same outer loop structure as DFS: iterate all cells and when a '1' is found, increment count and launch a traversal to sink the island. Instead of recursion, BFS uses an explicit queue. Enqueue the starting cell, mark it as '0' immediately (before processing), then process cells level by level, enqueuing and sinking each unvisited neighbor.

BFS is particularly useful for very large grids where Python's default recursion limit would cause a stack overflow with DFS. The explicit queue is allocated on the heap, so it is not subject to the call stack depth limit. In Java and C++ this distinction is less critical since recursion limits are not typically enforced by the language runtime.

Both BFS and DFS visit every cell at most once and produce the same island count. The choice is stylistic and situational. BFS code is slightly longer due to the queue boilerplate, but it avoids recursion depth issues. Many interviewers appreciate seeing both approaches demonstrated, as it shows fluency with the trade-offs.

Union-Find (Disjoint Set Union) treats each '1' cell as a node. During initialization, count all '1' cells as separate components. Then iterate all cells: for each '1' cell, check its right and down neighbors (checking all four is fine but right+down avoids double-processing edges). If a neighbor is also '1', union the two nodes. Each union that actually merges two different components decrements the component count.

The final component count equals the number of islands. Union-Find with path compression and union by rank runs in nearly O(m * n) time — formally O(m * n * alpha(m * n)) where alpha is the inverse Ackermann function, effectively O(m * n). Space is O(m * n) for the parent and rank arrays.

Union-Find shines in the follow-up problem Number of Islands II (LeetCode 305), where land cells are added dynamically one at a time. Each addition initializes a new node and unions it with adjacent land cells, returning the current island count after each addition. DFS and BFS would require re-scanning the entire grid after each addition, making them O(k * m * n) vs Union-Find's O(k * alpha(m * n)).

Python DFS (10 lines): def numIslands(grid): rows, cols = len(grid), len(grid[0]); count = 0. def dfs(i, j): if not (0<=i<rows and 0<=j<cols) or grid[i][j]=='0': return; grid[i][j]='0'; dfs(i+1,j); dfs(i-1,j); dfs(i,j+1); dfs(i,j-1). For i in range(rows): for j in range(cols): if grid[i][j]=='1': count+=1; dfs(i,j). Return count. Python BFS with deque: from collections import deque; replace dfs call with a while-queue loop enqueueing neighbors.

Java DFS: public int numIslands(char[][] grid) { int rows=grid.length, cols=grid[0].length, count=0; for(int i=0;i<rows;i++) for(int j=0;j<cols;j++) if(grid[i][j]=='1'){ count++; dfs(grid,i,j,rows,cols); } return count; } void dfs(char[][] grid, int i, int j, int rows, int cols){ if(i<0||i>=rows||j<0||j>=cols||grid[i][j]=='0') return; grid[i][j]='0'; dfs(grid,i+1,j,rows,cols); dfs(grid,i-1,j,rows,cols); dfs(grid,i,j+1,rows,cols); dfs(grid,i,j-1,rows,cols); }

Complexity summary: DFS time O(m*n), space O(m*n) worst-case call stack. BFS time O(m*n), space O(min(m,n)) average (BFS queue width) up to O(m*n) worst case. Union-Find time O(m*n * alpha(m*n)) ≈ O(m*n), space O(m*n) for parent and rank arrays. All three are effectively linear in the number of cells.

Surrounded Regions (LeetCode 130) is a direct cousin: instead of counting islands, you must flip all land cells not connected to the border to water. The key insight is to run DFS/BFS from all border land cells to mark the safe regions, then flip everything unmarked. The flood fill mechanics are identical to Number of Islands.

Pacific Atlantic Water Flow (LeetCode 417) runs two separate flood fills — one from Pacific-border cells and one from Atlantic-border cells — and returns cells reachable from both. Number of Islands II (LeetCode 305) is the dynamic variant where land cells are added one at a time; Union-Find is the optimal approach there because it supports incremental updates in nearly O(1) per addition. Rotting Oranges (LeetCode 994) uses multi-source BFS from all initially rotten cells simultaneously.

The unifying theme across this grid DFS/BFS family is connected component traversal: flood fill from a starting cell, mark all reachable cells, and use the count or state of components to answer the question. Number of Islands is the purest form of this pattern and is the recommended starting point before tackling the more complex variants.