Coding Interview Patterns Module 22 – Union-find (disjoint sets)
Connectivity and redundant edges
Find the line that closes the only loop of a network, answer connectivity questions as links arrive, and count islands as a bay is filled cell by cell.
What you will learn
- Find the line that closes the only loop of a network with one union per line
- Answer whether two items are connected at any moment while links arrive
- Count islands after each filled cell by numbering the cells r · cols + c
- Prove that the first union that fails is the line to switch off
- Extend the method to one-way feeders, lines that fail and spare cables
Before you start
What you’ll learn · Before you start
What you will learn
- Find the line that closes the only loop of a network with one union per line
- Answer whether two items are connected at any moment while links arrive
- Count islands after each filled cell by numbering the cells r · cols + c
- Prove that the first union that fails is the line to switch off
- Extend the method to one-way feeders, lines that fail and spare cables
Before you start
On this page
Redundant edges are links whose two ends were connected already, and union-find finds them as the links arrive. Put
each link into a union-find in the order it was made: the first one whose union returns False closed a loop. The
same structure answers connectivity questions at any moment, because two items are connected exactly when find
returns the same root for both. A grid becomes a union-find once cell (r, c) gets the number r · cols + c: a new land
cell adds one island, and each union with a land neighbour that returns True takes one away.
Both problems below build on the 20-line template of the union-find lesson.
Two problems from one growing network
Problem A: the line that closed the loop. An electricity board joined n substations, numbered 1 to n, with lines that carry power both ways, and logged each line as it was built. The plan was a tree, n − 1 lines and no loop, but the log has n lines, so there is exactly one loop. Switching off any line of that loop leaves a tree: return the one built last. Limits: 2 ≤ n ≤ 200,000; each line joins two different substations, and together they connect all of them.
n = 5with (1, 2), (2, 3), (3, 4), (1, 4), (4, 5) gives (1, 4).n = 6with (2, 3), (1, 2), (4, 5), (3, 1), (5, 6), (4, 1) gives (3, 1): the loop closes at the fourth line, and the two lines after it are still needed.n = 2with (1, 2), (2, 1) gives (2, 1): two lines between one pair form a loop.
Problem B: islands as a bay is filled. A bay of rows × cols cells is all water, and a reclamation project fills one cell at a time; a cell may be listed again. Land cells that share a side form one island. After each cell, report how many islands there are. Limits: 1 ≤ rows, cols ≤ 1,000 and at most 100,000 cells.
- 3 × 3 with (0, 0), (0, 2), (2, 1), (0, 1), (1, 1), (0, 1) gives 1, 2, 3, 2, 1, 1.
- 1 × 1 with (0, 0) twice gives 1, 1.
- 3 × 3 with (0, 1), (1, 0), (1, 2), (2, 1), (1, 1) gives 1, 2, 3, 4, 1: the centre joins four islands at once.
The first example of each problem
Text description of the diagram
The upper panel shows problem A on its first example. Substations 1, 2, 3 and 4 sit at the corners of a square and substation 5 to the left of 4. The lines are labelled in the order they were built: the 1st joins 1 and 2, the 2nd joins 2 and 3, the 3rd joins 3 and 4, the 4th joins 1 and 4, and the 5th joins 4 and 5. The 4th line is dashed: when it was built, the first three lines already connected 1 and 4, so union(1, 4) returned False and that line closed the only loop.
The lower panel shows problem B on its first example as three small grids of 3 by 3 cells. Land cells are shaded, and the cell just filled has a thick outline.
- After the 3rd cell, (2, 1), the land is (0, 0), (0, 2) and (2, 1): three islands of one cell each.
- After the 4th cell, (0, 1), the top row is all land and forms one island, and (2, 1) is another: two islands.
- After the 5th cell, (1, 1), the middle cell joins the top row to (2, 1): one island.
The brute force, and what it costs
For A, switch off each line in turn, the last one first, and search whether the other n − 1 lines still reach every substation. For B, fill the cell and flood every island of the bay again. Both are plainly right, and both are quadratic:
# Both problems by brute force, with the work counted. Correct by construction, so they are what faster code is
# checked against.
from collections import deque
def connects_all(n, lines):
"""BFS from substation 1 over these lines: do they reach all n substations? Also the line ends read."""
neighbours = [[] for _ in range(n + 1)]
for a, b in lines:
neighbours[a].append(b)
neighbours[b].append(a)
seen = [False] * (n + 1)
seen[1] = True
queue, reached, reads = deque([1]), 1, 0
while queue:
for other in neighbours[queue.popleft()]:
reads += 1
if not seen[other]:
seen[other] = True
reached += 1
queue.append(other)
return reached == n, reads
def loop_line_brute(n, lines):
"""Switch off each line in turn, the last built first, until the other n - 1 lines still reach every substation."""
work = 0
for k in range(len(lines) - 1, -1, -1):
ok, reads = connects_all(n, lines[:k] + lines[k + 1:])
work += reads
if ok:
return lines[k], work
return None, work
def count_islands(rows, cols, land):
"""Flood every island of the whole grid once; also the cells looked at."""
seen = [[False] * cols for _ in range(rows)]
islands, looked = 0, 0
for r in range(rows):
for c in range(cols):
looked += 1
if land[r][c] and not seen[r][c]:
islands += 1
seen[r][c] = True
queue = deque([(r, c)])
while queue:
y, x = queue.popleft()
for ny, nx in ((y - 1, x), (y + 1, x), (y, x - 1), (y, x + 1)):
if 0 <= ny < rows and 0 <= nx < cols:
looked += 1
if land[ny][nx] and not seen[ny][nx]:
seen[ny][nx] = True
queue.append((ny, nx))
return islands, looked
def islands_brute(rows, cols, cells):
"""Fill each cell, then count every island of the grid again."""
land = [[False] * cols for _ in range(rows)]
counts, work = [], 0
for r, c in cells:
land[r][c] = True
islands, looked = count_islands(rows, cols, land)
counts.append(islands)
work += looked
return counts, work
print("A: the line that closed the loop")
for n, lines in [
(5, [(1, 2), (2, 3), (3, 4), (1, 4), (4, 5)]),
(6, [(2, 3), (1, 2), (4, 5), (3, 1), (5, 6), (4, 1)]),
(2, [(1, 2), (2, 1)]),
]:
line, work = loop_line_brute(n, lines)
print(f" n = {n}: {line}, after {work} line ends read")
print("B: islands after each filled cell")
for rows, cols, cells in [
(3, 3, [(0, 0), (0, 2), (2, 1), (0, 1), (1, 1), (0, 1)]),
(1, 1, [(0, 0), (0, 0)]),
(3, 3, [(0, 1), (1, 0), (1, 2), (2, 1), (1, 1)]),
]:
counts, work = islands_brute(rows, cols, cells)
print(f" {rows} x {cols}: {counts}, after {work} cells looked at")
print("A when the loop closes early: a doubled first line, then a long chain")
for n in (500, 1_000, 2_000):
lines = [(1, 2), (2, 1)] + [(i, i + 1) for i in range(2, n)]
line, work = loop_line_brute(n, lines)
print(f" n = {n:>5,}: {line}, after {work:>9,} line ends read")Output
A: the line that closed the loop n = 5: (1, 4), after 16 line ends read n = 6: (3, 1), after 26 line ends read n = 2: (2, 1), after 2 line ends read B: islands after each filled cell 3 x 3: [1, 2, 3, 2, 1, 1], after 105 cells looked at 1 x 1: [1, 1], after 2 cells looked at 3 x 3: [1, 2, 3, 4, 1], after 91 cells looked at A when the loop closes early: a doubled first line, then a long chain n = 500: (2, 1), after 250,496 line ends read n = 1,000: (2, 1), after 1,000,996 line ends read n = 2,000: (2, 1), after 4,001,996 line ends read
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 brute_force.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
When the loop closes early, A reads about n² line ends, four times as many each time n doubles: about 4 × 10¹⁰ at n = 200,000. B looks at every cell after each filled cell, at least 10⁵ × 10⁶ = 10¹¹ looks at the limits. By the rough budgets of the constraints lesson, that is hours of Python and minutes of C++.
The key idea: a failed union, and a count that moves by one
Links are only ever added, the case union-find is made for.
- The loop. Feed the lines to a union-find in log order. The first union that returns False joins two substations that earlier lines connected already, so that line closed the loop.
- Connectivity at any moment. Between two lines, “can power flow from x to y?” is
find(x) == find(y), two finds and no search. - The islands. Number each cell r · cols + c and keep a list of the land cells. A new land cell is one more island; then union it with each neighbour that is land, and every union that returns True merges two islands into one. A cell that is land already changes nothing.
The same structure also handles links that point one way, links that fail instead of arriving, and spare cables that may be moved, with one change each. Each line and each cell costs a few finds, nearly constant time with union by size and path halving, plus the time to set up the arrays. Redundant edges are the only links whose union fails: in A the first of them is the answer, and in B they are the unions that leave the island count alone.
A dry run of both
The second example of A, with the roots that the two finds return:
| Line | Roots of its ends | union |
Loop? |
|---|---|---|---|
| (2, 3) | 2 and 3 | True | no |
| (1, 2) | 1 and 2 | True | no |
| (4, 5) | 4 and 5 | True | no |
| (3, 1) | 2 and 2 | False | yes: the answer |
The first example of B:
| Cell | Unions that merged | Islands |
|---|---|---|
| (0, 0), (0, 2), (2, 1) | none: three islands of one cell | 1, 2, 3 |
| (0, 1) | with (0, 0) and (0, 2) | 3 + 1 − 2 = 2 |
| (1, 1) | with (0, 1) and (2, 1) | 2 + 1 − 2 = 1 |
| (0, 1) | land already: skipped | 1 |
Exercise
Exercise · Medium · Python, JavaScript
Islands after each filled cell
A bay is a grid of rows × cols cells, all water at first. A reclamation project fills one cell with land at a time. Write islands_after_each(rows, cols, cells) (islandsAfterEach(rows, cols, cells) in JavaScript): cells lists the filled cells in order as (r, c) pairs, row first, and the function returns one number per cell, the number of islands right after that cell is filled. Land cells that share a side belong to the same island; cells that touch only at a corner do not.
islands_after_each(3, 3, [(0, 0), (0, 2), (2, 1), (0, 1), (1, 1), (0, 1)]) # [1, 2, 3, 2, 1, 1]The fourth cell joins the two islands of the top row, and the fifth joins that island with the one at the bottom. The last cell is land already: filling it again changes nothing.
- A cell may be listed more than once.
- The sample tests include a grid of 1,000 × 1,000 cells with 100,000 filled cells, so counting every island again after each cell is far too slow.
- Limits: 1 ≤
rows,cols≤ 1,000 and at most 100,000 cells.
Python · Starter code · islands.py
def islands_after_each(rows, cols, cells):
"""After each filled cell (r, c), the number of islands. One number per cell."""
# Replace this line with your code.
return []The sample tests · test_islands.py
import random
from collections import deque
from islands import islands_after_each
def trusted(rows, cols, cells):
"""The answer the tests trust: after each cell, flood every island of the land again."""
land, counts = set(), []
for cell in cells:
land.add(tuple(cell))
seen, islands = set(), 0
for start in land:
if start in seen:
continue
islands += 1
seen.add(start)
queue = deque([start])
while queue:
r, c = queue.popleft()
for nxt in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
if nxt in land and nxt not in seen:
seen.add(nxt)
queue.append(nxt)
counts.append(islands)
return counts
def test_example():
"""the example of the prompt: 1, 2, 3, 2, 1, 1"""
assert islands_after_each(3, 3, [(0, 0), (0, 2), (2, 1), (0, 1), (1, 1), (0, 1)]) == [1, 2, 3, 2, 1, 1]
def test_no_cells():
"""no cells, no numbers"""
assert islands_after_each(2, 2, []) == []
def test_refilled_cell():
"""filling a cell that is land already changes nothing"""
assert islands_after_each(1, 1, [(0, 0), (0, 0), (0, 0)]) == [1, 1, 1]
def test_one_cell_joins_four():
"""the centre of a plus joins four islands at once: 4 becomes 1"""
assert islands_after_each(3, 3, [(0, 1), (1, 0), (1, 2), (2, 1), (1, 1)]) == [1, 2, 3, 4, 1]
def test_corners_do_not_join():
"""cells that touch only at a corner are separate islands"""
assert islands_after_each(2, 2, [(0, 0), (1, 1), (0, 1)]) == [1, 2, 1]
def test_rows_do_not_wrap():
"""the end of one row is not next to the start of the next"""
assert islands_after_each(2, 3, [(0, 2), (1, 0)]) == [1, 2]
assert islands_after_each(3, 1, [(0, 0), (2, 0), (1, 0)]) == [1, 2, 1]
def test_large_bay():
"""1,000 x 1,000 cells: 50,000 single cells, then the gaps of their rows filled"""
singles = [(r, c) for r in range(0, 1000, 2) for c in range(0, 200, 2)]
gaps = [(r, c) for r in range(0, 1000, 2) for c in range(1, 200, 2)]
counts = islands_after_each(1000, 1000, singles + gaps)
assert len(counts) == 100_000
assert counts[49_999] == 50_000
assert counts[-1] == 500
def test_random_against_recount():
"""300 random bays of up to 5 x 5 cells, checked against a full recount after every cell"""
rng = random.Random(7)
for _ in range(300):
rows, cols = rng.randint(1, 5), rng.randint(1, 5)
cells = [(rng.randrange(rows), rng.randrange(cols)) for _ in range(rng.randint(0, 20))]
assert islands_after_each(rows, cols, cells) == trusted(rows, cols, cells), (rows, cols, cells)JavaScript · Starter code · islands.mjs
/**
* After each filled cell [r, c], the number of islands. Returns one number per cell.
* The bay has rows x cols cells, all water at first.
*/
export function islandsAfterEach(rows, cols, cells) {
// Replace this line with your code.
return [];
}The sample tests · islands.test.mjs
import { test, assert } from 'mysmartcopilot:test';
import { islandsAfterEach } from './islands.mjs';
let seed = 7;
const random = () => (seed = (seed * 48271) % 2147483647) / 2147483647;
const randInt = (lo, hi) => lo + Math.floor(random() * (hi - lo + 1));
// The answer the tests trust: after each cell, flood every island of the land again.
function trusted(rows, cols, cells) {
const land = new Set();
const counts = [];
for (const [r, c] of cells) {
land.add(r * cols + c);
const seen = new Set();
let islands = 0;
for (const start of land) {
if (seen.has(start)) continue;
islands += 1;
seen.add(start);
const queue = [start];
for (let head = 0; head < queue.length; head++) {
const cell = queue[head];
const y = Math.floor(cell / cols);
const x = cell % cols;
for (const [ny, nx] of [[y - 1, x], [y + 1, x], [y, x - 1], [y, x + 1]]) {
const next = ny * cols + nx;
if (ny >= 0 && ny < rows && nx >= 0 && nx < cols && land.has(next) && !seen.has(next)) {
seen.add(next);
queue.push(next);
}
}
}
}
counts.push(islands);
}
return counts;
}
test('the example of the prompt: 1, 2, 3, 2, 1, 1', () => {
assert.deepEqual(islandsAfterEach(3, 3, [[0, 0], [0, 2], [2, 1], [0, 1], [1, 1], [0, 1]]), [1, 2, 3, 2, 1, 1]);
});
test('no cells, no numbers', () => {
assert.deepEqual(islandsAfterEach(2, 2, []), []);
});
test('filling a cell that is land already changes nothing', () => {
assert.deepEqual(islandsAfterEach(1, 1, [[0, 0], [0, 0], [0, 0]]), [1, 1, 1]);
});
test('the centre of a plus joins four islands at once: 4 becomes 1', () => {
assert.deepEqual(islandsAfterEach(3, 3, [[0, 1], [1, 0], [1, 2], [2, 1], [1, 1]]), [1, 2, 3, 4, 1]);
});
test('cells that touch only at a corner are separate islands', () => {
assert.deepEqual(islandsAfterEach(2, 2, [[0, 0], [1, 1], [0, 1]]), [1, 2, 1]);
});
test('the end of one row is not next to the start of the next', () => {
assert.deepEqual(islandsAfterEach(2, 3, [[0, 2], [1, 0]]), [1, 2]);
assert.deepEqual(islandsAfterEach(3, 1, [[0, 0], [2, 0], [1, 0]]), [1, 2, 1]);
});
test('1,000 x 1,000 cells: 50,000 single cells, then the gaps of their rows filled', () => {
const cells = [];
for (let r = 0; r < 1000; r += 2) for (let c = 0; c < 200; c += 2) cells.push([r, c]);
for (let r = 0; r < 1000; r += 2) for (let c = 1; c < 200; c += 2) cells.push([r, c]);
const counts = islandsAfterEach(1000, 1000, cells);
assert.equal(counts.length, 100000);
assert.equal(counts[49999], 50000);
assert.equal(counts[counts.length - 1], 500);
});
test('300 random bays of up to 5 x 5 cells, checked against a full recount after every cell', () => {
for (let trial = 0; trial < 300; trial++) {
const rows = randInt(1, 5);
const cols = randInt(1, 5);
const cells = Array.from({ length: randInt(0, 20) }, () => [randInt(0, rows - 1), randInt(0, cols - 1)]);
assert.deepEqual(islandsAfterEach(rows, cols, cells), trusted(rows, cols, cells), JSON.stringify([rows, cols, cells]));
}
});A hint
Give every cell a number, r * cols + c, and make a union-find over all of them, plus a list that says which cells are land. A new land cell is an island of its own until you look at its four neighbours: each neighbour that is land and not yet in the same set is one merge, and every merge leaves one island fewer.
Results of the sample tests
| Test | Result | Details |
|---|
What your code printed
The sample tests run on this device, in your browser (Pyodide, QuickJS): nothing is sent to mysmartcopilot.com. The first run of each language downloads it: Python (about 13.5 MB) or JavaScript (about 0.6 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.
Check yourself
4 questions about this lesson. Every answer and why it is right is on the page, behind “Show the answer”. Your score stays in this browser.
Both problems proved, in five languages, and tested Pro: opens with a Pro, Premium or Ultimate pass
A loop of union-find calls is short, but it is right only for a reason. Each solution gets its proof here, then the code in Python, JavaScript, Java, C++ and Go with what each printed, and a comparison with the brute forces on 4,000 random cases.
In this part:
- Why the first failed union is the line to switch off
- Why the island count stays right
- The code in five languages
- Checked against the brute forces on 4,000 random cases
3 runnable examples (C++, Go, Java, JavaScript, Python) · about 4 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Islands at scale, and six bugs reproduced Pro: opens with a Pro, Premium or Ultimate pass
The island count has to stay right when a million cells and a hundred thousand fills are involved. This part measures the work of both methods as the bay grows and runs six plausible bugs until each one breaks.
In this part:
- The work measured: a full recount against union-find
- Six bugs and the smallest inputs that break them
2 runnable examples (Python) · about 3 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Questions between links, one-way feeders, failures and spare cables Pro: opens with a Pro, Premium or Ultimate pass
Four problems change one thing about the setting: questions arrive between the links, the links point one way, links fail instead of arriving, or cables may be moved. Each is solved below with the same union-find, and three of them are checked against a brute force.
In this part:
- Questions between links, answered in nearly constant time
- One-way feeders: two parents or a loop
- Lines that fail: walk back in time
- Spare cables: one move per missing link
- A practice set with sample answers
1 runnable example (Python) · about 3 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Interview questions
-
Fresher to mid · Warm-up
Land cells are added to a grid one at a time, and a union-find keeps the island count. Why does a new cell change the count by +1, and then by −1 for each union with a land neighbour that returns True?
A new land cell touches no other land until it is joined to its neighbours, so at first it is an island of its own: +1. Each neighbour that is land belongs to some island. A union with that neighbour returns True only when its island is not yet in the same group as the new cell, and then two islands become one: −1. A union that returns False means the neighbour's island was joined already through another side of the new cell, so nothing changes. A cell between two islands therefore gives +1 − 2 = −1, and the centre of a plus of four islands gives +1 − 4 = −3. A cell that is land already must be skipped before any of this, or it adds an island that no union takes away.
-
Mid to senior
A power network is a rooted tree: one main station, and every other station fed by exactly one one-way feeder. Its log of n feeders has one feeder too many. Which feeder do you remove so that the rest is a rooted tree again, taking the one logged last when several would work?
-
Mid to senior
A survey grid has 10⁹ × 10⁹ cells, and 200,000 of them become land one at a time. After each, report the number of islands. Arrays of rows × cols entries are out of the question. What do you build, and how much memory and time does it need?
-
Fresher to mid
A lab has n computers joined by m cables, and some computers cannot reach each other. A move unplugs one cable and plugs it in between any two computers. What is the smallest number of moves that connects every computer, or −1 if no number does? Explain why it is the minimum.
Key takeaways
- A union that returns False joins items that were connected already; in a growing network, the first one closed the loop.
- Whether two items are connected at any moment is
find(x) == find(y). - With cell (r, c) numbered r · cols + c, a new land cell adds one island and each merge with a land neighbour takes one away.
References
- Efficiency of a Good But Not Linear Set Union Algorithm (R. E. Tarjan, Journal of the ACM 22(2), 1975) (Association for Computing Machinery (ACM))
- Worst-case Analysis of Set Union Algorithms (R. E. Tarjan and J. van Leeuwen, Journal of the ACM 31(2), 1984) (Association for Computing Machinery (ACM))
- Dictionary of Algorithms and Data Structures: tree (National Institute of Standards and Technology (NIST))
- collections.deque (The Python Standard Library) (Python Software Foundation)
- Uint8Array (MDN Web Docs)
- The Java Language Specification, Java SE 25: 4.12.5 Initial Values of Variables (Oracle)
- JEP 330: Launch Single-File Source-Code Programs (OpenJDK)
- Working Draft, Programming Languages: C++ (N4950), 5.11 Keywords [lex.key] (ISO/IEC JTC1/SC22/WG21)
- The Go Programming Language Specification: For statements with range clause (The Go Authors)
- AddressSanitizer (Clang documentation) (LLVM Project)
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress