LeetMotion
Given a 2D grid where "1" is land and "0" is water, return the number of islands. Islands connect only in 4 directions: up, down, left, and right.
We can treat each unvisited land cell as the start of a new island and run DFS/BFS to consume the whole component.
Imagine surveying a vast, uncharted archipelago from a hot air balloon. Every time you spot a raised piece of land (a 1), you've discovered a new island! To make sure you don't count the same island twice, you command the ocean to rise, temporarily flooding the island (turning it into a 0) as you explore its shores.
Use preset scenarios below to see the DFS algorithm discover and flood different island formations.
"0" or use a visited set) before exploring neighbors.If you launch DFS/BFS from every land cell without persisting visited state, the same island gets traversed repeatedly. Proper marking guarantees each cell is processed at most once.
Why do it this way? The most natural way to find all connected land is to physically "walk" across it. When we scan the grid and find a piece of land (1), we know we've discovered a new island. To avoid counting it again later, we can launch a Depth-First Search (DFS) to explore every connected piece of that island and "sink" it by changing it to a 0. This is incredibly efficient because we only ever visit each cell a constant number of times.
function numIslands(grid):
islands = 0
rows = grid.length
cols = grid[0].length
function dfs(r, c):
// Stop if out of bounds or if cell is water
if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == '0':
return
// Sink the land so we don't visit it again
grid[r][c] = '0'
// Explore all 4 neighbors
dfs(r - 1, c)
dfs(r + 1, c)
dfs(r, c - 1)
dfs(r, c + 1)
// Scan every cell in the grid
for r from 0 to rows - 1:
for c from 0 to cols - 1:
// If we find unvisited land, it's a new island
if grid[r][c] == '1':
islands += 1
dfs(r, c) // Sink the entire island
return islandsThe most common bug in grid traversal is forgetting to check boundaries before accessing grid[r][c]. Always ensure r >= 0, c >= 0, r < rows, and c < cols before doing anything else.
If you forget to mutate the grid (`grid[r][c] = "0"`) or maintain a separate visited set, your DFS will bounce back and forth between two adjacent land cells infinitely until the call stack crashes.
In some interview settings, the interviewer will ask you not to modify the input grid. In that case, sinking the island (`grid[r][c] = "0"`) isn't allowed. You must instantiate a separate visited = set() and add `(r, c)` tuples to keep track of explored land. This increases space complexity but preserves the original data.
Discussion
…