Most Stones Removed with Same Row or Column
01 · Problem
Stones are placed at distinct integer points on a 2D grid, given as stones[i] = [row, col].
You may remove a stone if, at the moment of removal, another stone still on the board shares its row or its column. You may perform removals in any order.
Return the largest number of stones that can be removed.
02 · Examples
stones = [[0,0],[0,2],[1,1],[2,1]]
2
Stones (0,0) and (0,2) share row 0, so one of them can be removed. Stones (1,1) and (2,1) share column 1, so one of them can be removed. Two stones are left, one per group, so 2 are removed.
stones = [[0,0]]
0
A single stone has no partner, so nothing can be removed.
stones = [[0,1],[1,0],[1,1]]
2
All three stones are linked: (1,1) shares row 1 with (1,0) and column 1 with (0,1). Remove (1,0), then (0,1) still shares column 1 with (1,1), so remove it too. 2 stones are removed.
03 · Constraints
- 011 <= stones.length <= 1000
- 020 <= row, col <= 104
- 03No two stones are at the same point
04 · Optimal complexity
- Time
- O(n * alpha(n))
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.