Most Stones Removed with Same Row or Column

MediumGraphsunion find

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

There are n stones on a 2D grid, each at a distinct integer coordinate stones[i] = [x, y]. A stone may be removed if at least one **other** stone that has not been removed yet shares its row (x) or its column (y). Removals happen one at a time, and the order is up to you. Return the largest number of stones that can be removed.

Examples

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5
All six stones are linked through shared rows and columns into one group, and a group of `k` linked stones can always be reduced to a single stone, so 5 can be removed.
Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3
The corners form one group of 4 (remove 3), while `[1,1]` shares no row or column with anything.

Constraints

  • 1 <= stones.length <= 1000
  • 0 <= x, y <= 10^4
  • No two stones share the same coordinate

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More union find problems