Number of islands with DFS vs BFS vs Union-Find — trade-offs?

Q: Number of islands with DFS vs BFS vs Union-Find — trade-offs?

**Target Audience:** Candidates who can already solve number of islands once and want to compare the three standard approaches **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged `📌 Interview term:` with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the **Verified** section is copied from that run. ## 1. Why This Even Matters — A Story First Three surveyors are sent to count the islands of a newly mapped archipelago. **The hiker (DFS)** lands on the first unvisited beach and walks inland as far as she can, then retraces her steps to try every side path, planting a flag on each square. Her notebook only holds the trail back to where she started — but on a huge, winding island that trail can get very long. **The search

The problem

Question presented to candidate: "You have solved number of islands with DFS. Now compare DFS, BFS and Union-Find for this problem — their costs, their risks, and when you would choose each — and implement the Union-Find version in Python."

What a strong answer should cover:

All three are O(rows × cols) for a single count (Union-Find with path compression and union by size is O(α(n)) per operation, effectively constant).
Memory shape: DFS stack (or recursion) vs BFS queue vs Union-Find's full parent/size arrays; recursive DFS can hit the recursion limit.
Union-Find counts as land − successful unions, looking only right and down from each cell.
Union-Find shines when land arrives incrementally (Number of Islands II); it cannot handle removals; BFS is the one that gives distances.
Python details: iterative find (no recursion), list(range(n)) for parent, collections.deque for BFS, and the 1000-frame recursion limit for recursive DFS.

Code / implementation expected: Yes — a Union-Find (with path halving and union by size) over cell ids r * cols + c, in Python.

dfs
bfs
Meta

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Candidates who can already solve number of islands once and want to compare the three standard approaches
Difficulty: Medium
Language: Python 3

How to read this doc: every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged 📌 Interview term: with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the Verified section is copied from that run.

1. Why This Even Matters — A Story First

Three surveyors are sent to count the islands of a newly mapped archipelago.

The hiker (DFS) lands on the first unvisited beach and walks inland as far as she can, then retraces her steps to try every side path, planting a flag on each square. Her notebook only holds the trail ba

The solution is hidden so you can try first

8 min read · 12 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonDFS vs BFS vs Union-Find: same counts, different peak memory

Practice

PythonNumber of Islands II: Union-Find vs recounting with BFS

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.