PPractick

The problem

A map starts as all water. Land is added one cell at a time, as volcanic islands rising from the sea, and after each addition the dashboard must show the current number of islands (4-directionally connected land). Re-running a flood fill after every addition costs O(m · n) each time. Union-find handles it online. A new land cell adds one island, and every successful union with a neighbouring land cell merges two islands, subtracting one. Adding a cell that's already land changes nothing.

Example: 3 × 3 grid, additions (0,0), (0,1), (1,2), (2,1) → [1, 1, 2, 3].

Function signature

vector<int> numIslands2(int m, int n, const vector<pair<int, int>>& positions);

Test cases

Input (m, n, positions)	Output	Explanation
(3, 3, [[0,0],[0,1],[1,2],[2,1]])	[1, 1, 2, 3]	(0,1) joins (0,0)
(2, 2, [[0,0],[1,1],[0,1]])	[1, 2, 1]	(0,1) bridges two islands
(1, 3, [[0,0],[0,2],[0,1]])	[1, 2, 1]
(3, 3, [[0,0],[0,0]])	[1, 1]	A repeat addition changes nothing
(1, 1, [[0,0]])	[1]

(Confirm: connectivity is 4-directional; positions may repeat; the grid starts as all water.)

How interviewers phrase it

• "Given an m x n water grid and a list of positions to turn into land, return the number of islands after each operation" (LeetCode 305).

Clarifying questions to ask

1. Can a position repeat? (Yes, and then the count is unchanged.)
2. 4-directional? (Yes.)
3. How many operations? (Up to 10⁴ on a large grid, so per-operation BFS is too slow.)

Follow-ups to expect

1. "Why union-find?"
2. "How does the count change?"
3. "Why check roots before decrementing?"
4. "What if land could also disappear?"
5. "Complexity?"

Related questions

• Disjoint Set Hard
• Accounts merge Hard
• Most stones removed with same row or column Medium
• Number of operations to make network connected Hard
• Making a large island Hard
• Number of provinces Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in