Depth-First Search
Medium
Number of Islands
Count the number of connected groups of 1s in a grid.
10 min read
Solve on LeetCodeExamples
Input:grid = [['1','1','0'], ['1','1','0'], ['0','0','1']]
Output:2
Explain:
Island 1 (Top Left), Island 2 (Bottom Right).
Problem Understanding
Given an m x n map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and formed by connecting adjacent lands horizontally or vertically.
Algorithm Strategy
We need to find Connected Components.
- Iterate: Loop through every cell
(r, c)of the grid. - Trigger: If we find a land cell
'1', we found a NEW island!- Increment
count. - Sink the Island: Launch DFS from this cell to visit all connected lands and mark them as visited (e.g., change '1' to '0').
- Increment
- Continue: If we see a '0' (or visited cell), skip it.
Visualization
Step 1 / 30
1
1
0
0
0
1
1
0
0
1
1
1
0
0
0
1
1
0
0
1
0
0
0
0
1
1
0
0
1
1
Problem: Count the number of islands (connected groups of 1s).
1x
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.