Number of Islands

Number of Islands

What is this problem about?

The Number of Islands problem gives you a 2D binary grid where '1' represents land and '0' represents water. Count the number of islands — groups of connected '1' cells (4-directional connectivity). This Number of Islands coding problem is the most widely asked graph traversal problem in all of technical interviews.

Why is this asked in interviews?

This problem is asked by virtually every major tech company: Google, Amazon, Meta, Microsoft, Apple, Bloomberg, Uber, and hundreds more. It is the definitive test of BFS/DFS on grids and serves as a template for dozens of related problems. The array, matrix, union find, BFS, and DFS interview pattern is the cornerstone of grid problem-solving.

Algorithmic pattern used

DFS or BFS flood-fill. For each unvisited '1' cell, run a DFS/BFS that marks all connected land cells as visited ('0' or a separate visited marker). Each DFS/BFS invocation = one island. Count total invocations.

Union-Find alternative: Initialize each '1' cell as its own component. For each pair of adjacent '1' cells, union them. Count final components.

Example explanation

Grid:

1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

• DFS from (0,0): marks (0,0),(0,1),(1,0),(1,1). Island 1.
• DFS from (2,2): marks (2,2). Island 2.
• DFS from (3,3): marks (3,3),(3,4). Island 3. Total = 3 islands.

Common mistakes candidates make

• Not marking cells as visited (infinite recursion or wrong count).
• Using 8-directional connectivity instead of 4-directional (problem specifies 4).
• Modifying the input grid vs using a separate visited array (both work, clarify with interviewer).
• DFS stack overflow for very large grids (use iterative BFS instead).

Interview preparation tip

Number of Islands must be mastered completely. Implement DFS, iterative BFS, and Union-Find solutions. Know when to use each: DFS is simplest to code, BFS avoids stack overflow, Union-Find handles dynamic updates. The flood-fill template — for each cell of target type, DFS to mark its connected region — applies to 50+ grid problems. Practice until you can implement all three versions in under 10 minutes combined.