Number of Islands

Grid

Current Cell

Scanning

Islands Found

DFS Stack

DFS Stack / BFS Queue

Empty

Click "Step" or "Play" to start the visualization

Water (0)

Land (1)

Current

Visited

Python Code - DFS Approach

                for i in range(rows):
            
                    for j in range(cols):
            
                        if grid[i][j] == "1" and not visited[i][j]:
            
                            islands += 1
            
                            dfs(i, j) # mark all connected land
            
                def dfs(i, j):
            
                    visited[i][j] = True
            
                    for di, dj in [(-1,0),(0,1),(1,0),(0,-1)]:
            
                        if valid(i+di, j+dj) and not visited:
            
                            dfs(i+di, j+dj)

Complexity Analysis

Time Complexity O(m × n) Space Complexity O(m × n)

Time Complexity: O(m × n)

Breakdown

Main loop visits each cell once: O(m × n)
DFS visits each land cell at most once total
Each cell has ≤ 4 neighbors checked
Marking visited: O(1) per cell

T(m,n) = O(m × n) + O(4 × m × n) = O(m × n)

Mathematical Intuition

The grid is an implicit graph with m×n vertices and ≤ 4×m×n edges (4-connectivity). DFS on a graph is O(V + E). Since E = O(V) in a grid, total time is O(m × n). Each cell is processed exactly once: either by the main loop (water) or by DFS (land, then marked).

Key Insight

Counting connected components via DFS/BFS is a standard graph traversal pattern—the key is ensuring each vertex is visited exactly once.

Space Complexity: O(m × n)

Breakdown

Recursion stack: O(m × n) worst case
Visited markers: O(1) if modifying grid in-place
Separate visited array: O(m × n) if preserving input
BFS queue alternative: O(min(m, n))

S(m,n) = O(m × n) for recursion stack depth

Mathematical Intuition

The worst-case recursion depth occurs when the entire grid forms a single snake-like island (e.g., a spiral). In this case, DFS may recurse through all m×n cells before returning. BFS limits queue size to the current frontier, which is O(min(m,n)) for a connected component.

Key Insight

Iterative DFS with explicit stack or BFS can avoid stack overflow for large grids, trading recursion elegance for robustness.