Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Number of Islands

LeetCode #200Medium
Count components, sink each island

Given a grid of land and water cells, count the number of islands, where an island is a group of land cells connected 4-directionally and surrounded by water.

Asked atAmazonGoogleMetaMicrosoft
step 1 / 23
4 × 5 map · 1 = land, 0 = water
1
1
0
0
1
1
0
0
1
1
0
0
0
0
0
1
1
0
0
0
Scan + DFS sink
▸
1count = 0
2for each cell (r, c):
3    if already water/sunk: continue
4    if grid[r][c] == 1:
5        count++
6        sink(r, c):
7            grid[r][c] = 0
8            for each land neighbour: sink it
9return count
state
  • size4 × 5
  • count0

line 1Count the islands: maximal blobs of 1 (land) connected up/down/left/right; 0 is water. This is a connected-components count. Scan the grid row by row; the FIRST time we step onto a piece of an undiscovered island, we add one to the counter and then DFS-flood that entire island so we never count it twice.