DSA interview question

Most Stones Removed with Same Row or Column

Medium · Data structures · Topics: graph, dsu, union find

The problem

A puzzle board has stones on integer grid points. A stone can be removed if another remaining stone shares its row or its column. What's the maximum number of stones that can be removed? Stones that share a row or column are linked, and linking is transitive, so the board splits into connected groups. Each group can be removed down to a single stone (remove them in reverse DFS order from a leaf), but never to zero. So the answer is stones − number of groups, and union-find computes the groups by linking each stone to the first stone seen in its row and in its column.

Example: [[0,0], [0,1], [1,0], [1,2], [2,1], [2,2]] → 5.

Function signature

int removeStones(const vector<pair<int, int>>& stones);  // distinct positions

Test cases

Input (stones)	Output	Explanation
`[[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]`	`5`	One group of 6
`[[0,0],[0,2],[1,1],[2,0],[2,2]]`	`3`	The groups have 4 and 1 stones
`[[0,0],[0,1],[0,2]]`	`2`	One row
`[[0,0],[1,1]]`	`0`	Nothing is shared
`[[0,0]]`	`0`

(Confirm: positions are distinct; a stone needs a remaining partner in its row or column at the moment it's removed.)

How interviewers phrase it

"Return the largest possible number of stones that can be removed, where a stone can be removed if it shares a row or column with another stone that has not been removed" (LeetCode 947).

Clarifying questions to ask

Is the order of removals free? (Yes: the question asks for the maximum.)
Distinct positions? (Yes.)
How large are the coordinates? (Up to 10⁴, so use maps or offsets.)

Follow-ups to expect

"Why can every group be reduced to one stone?"
"Why can't a group vanish entirely?"
"How do you union efficiently?"
"O(n²) alternative?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview