Browse Curriculum

FAANGPrep Sprint

Medium

Number of Islands

Count the number of connected groups of 1s in a grid.

10 min read

Time: O(n)

Space: O(1)

Solve on LeetCode

Examples

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').
Continue: If we see a '0' (or visited cell), skip it.

Visualization

Step 1 / 30

Problem: Count the number of islands (connected groups of 1s).

Custom Input

Watch as we iterate through the grid. When we hit land, invalidating the entire connected chunk.

Dry Run

Board:

1 1 0
1 0 0
0 0 1

Step	Cell (r,c)	Val	Action	Island Count	Grid State
1	(0,0)	'1'	New Island! Count = 1. Start DFS.	1	Sink (0,0) -> '0'
2	DFS(0,0)	-	Visit neighbors (0,1), (1,0)...	1	Sink (0,1), (1,0) -> '0'
3	(0,1)	'0'	Already visited (sunk). Skip.	1	-
4	(0,2)	'0'	Water. Skip.	1	-
...	...	...	...	...	...
5	(2,2)	'1'	New Island! Count = 2. Start DFS.	2	Sink (2,2) -> '0'
End	-	-	All cells visited.	2	All '0'

Edge Cases & Common Mistakes

Out of Bounds: Always check r < 0, c < 0, r >= rows, c >= cols first in DFS.
Cyclic Dependency: Without marking visited (or changing '1' to '0'), DFS will run infinitely in a loop of lands.
Empty Grid: Dimensions 0x0. Return 0.
Diagonal Connection: The problem usually specifies horizontal/vertical connections only (4-way). Don't include diagonals unless specified.

Solution (Sinking Method)

Modifying the grid in-place to save space.

1class Solution:
2    def numIslands(self, grid: List[List[str]]) -> int:
3        if not grid: return 0
4        rows, cols = len(grid), len(grid[0])
5        islands = 0
6        
7        def dfs(r, c):
8            # Check Bounds and Water
9            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
10                return
11            
12            # Mark as visited (Sink)
13            grid[r][c] = '0'
14            
15            # Recurse 4 directions
16            dfs(r+1, c)
17            dfs(r-1, c)
18            dfs(r, c+1)
19            dfs(r, c-1)
20            
21            # Note: For BFS, you would use a Queue here.
22            
23        for r in range(rows):
24            for c in range(cols):
25                if grid[r][c] == '1':
26                    islands += 1
27                    dfs(r, c)
28                    
29        return islands

Complexity Analysis

Time: O(M * N). We visit each cell once.
Space: O(M * N) worst case for DFS stack (if entire grid is land).