FAANGPrep Sprint

Number of Islands

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

MediumSolve 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

An m x n grid marks land with '1' and water with '0'. Count the islands: groups of land cells joined through up, down, left or right neighbours, with water or the grid's edge all around them.

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

1 = LAND · 0 = WATER · COLOURED 0 = SUNK WITH ITS ISLAND

NEW ISLAND

islands

Answer

—

call stack

No dfs running

islands found

#1: 0 cells

(0, 0) is '1' — land no DFS has reached: islands = 1. Sink it

dfs(0, 0): land — sink it to '0' as part of island #1

grid

Legend & Complexity

The cell whose dfs call is running, or the land that starts a new island

A sunk cell whose call is waiting on a deeper one

Sunk — each island keeps its own colour, listed beside the grid

Time

O(m·n)

Space

O(m·n) call stack

Scan the grid row by row. When the scan finds land, the island counter goes up and DFS sinks every cell of that island to '0', calling down, up, right, then left. Each island keeps its own colour after it is sunk, so when the scan later passes over those cells you can see they were already counted.

Dry Run

Grid:

1 1 0
1 0 0
0 0 1

Step	Where	Action	Islands
1	scan `(0,0)`	`'1'` — new island. `islands = 1`. Call `dfs(0,0)`.	1
2	`dfs(0,0)`	Sink `(0,0)`. Call down.	1
3	`dfs(1,0)`	Sink `(1,0)`. Down `(2,0)` is water, up `(0,0)` is already sunk, right `(1,1)` is water, left `(1,-1)` is outside — all return.	1
4	back in `dfs(0,0)`	Up `(-1,0)` is outside — returns. Call right.	1
5	`dfs(0,1)`	Sink `(0,1)`. Down `(1,1)` is water, up `(-1,1)` is outside, right `(0,2)` is water, left `(0,0)` is already sunk — all return.	1
6	back in `dfs(0,0)`	Left `(0,-1)` is outside — returns. The first island is fully sunk.	1
7	scan `(0,1)` to `(2,1)`	`(0,1)` and `(1,0)` are now `'0'`; `(0,2)`, `(1,1)`, `(1,2)`, `(2,0)` and `(2,1)` are water — all skipped.	1
8	scan `(2,2)`	`'1'` — new island. `islands = 2`. Call `dfs(2,2)`.	2
9	`dfs(2,2)`	Sink `(2,2)`. Down and right are outside; up `(1,2)` and left `(2,1)` are water — all return.	2
End	—	Every cell scanned. Return 2.	2

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.
All Water: No cell is 1, so no DFS ever starts and the answer is 0. (LeetCode guarantees at least one row and one column.)
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.

Number of Islands Code

1var numIslands = function(grid) {
2    const rows = grid.length, cols = grid[0].length;
3
4    function dfs(r, c) {
5        if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== '1') {
6            return;
7        }
8        grid[r][c] = '0';
9        dfs(r + 1, c);
10        dfs(r - 1, c);
11        dfs(r, c + 1);
12        dfs(r, c - 1);
13    }
14
15    let islands = 0;
16    for (let r = 0; r < rows; r++) {
17        for (let c = 0; c < cols; c++) {
18            if (grid[r][c] === '1') {
19                islands++;
20                dfs(r, c);
21            }
22        }
23    }
24    return islands;
25};