AlgoViz
HomeGraphs

Connected Components Problem in Matrix

Medium

Islands, counted by traversal

Problem

Count connected groups of 1s (4- or 8-directionally) in a binary matrix.

In simple words

Scan the grid; each time you find unvisited land, flood-fill its whole island and count it once.

The idea

Each land cell is a vertex adjacent to its neighbouring land cells, so a component is an island. Sweep the grid and start a traversal at every unvisited 1, sinking the whole island as you go.

The trick

  • Sink the island by overwriting the cells, avoiding a separate visited grid.
  • Decide up front whether diagonals count — it changes the direction list.
  • O(rows × cols).
1
1
0
0
1
0
0
1
0
0
1
1
0
0
0
1

Step 1 of 9. Scan for land. Each unvisited '1' starts a new island; flood-fill its whole blob so it isn't counted twice.

1/9
Optimal
timeO(rows·cols)spaceO(rows·cols)

Sink each island you find.

1for (r, c) if (grid[r][c] === '1') {2  islands++;3  sink(r, c); // DFS marks the blob as water4}5function sink(r, c) {6  if (out of bounds || grid[r][c] !== '1') return;7  grid[r][c] = '0';8  for (const [dr, dc] of DIRS) sink(r+dr, c+dc);9}

Input

grid
4 × 4

Memory

at
—
cells marked
0

Output

islands
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
grid = [[1,1,0],[0,1,0],[0,0,1]]
Output:
2
Explanation:
One connected blob of 1s plus a lone 1 → 2 islands.

Example 2

Input:
grid = [[1,1,1],[1,1,1]]
Output:
1
Explanation:
All land is connected → a single island.

Example 3

Input:
grid = [[0,0],[0,0]]
Output:
0
Explanation:
All water → no islands.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.