Most Stones Removed with Same Row or Column

Standard Bar Graphs · MST Problems O(n α(n)) · O(n)

Clearing the Pallet Grid One Clutch at a Time

A robotic crane works over a floor where pallets sit on integer grid coordinates. A pallet is liftable whenever another pallet shares its row or its column. The foreman wants to clear as many pallets as possible through legal single lifts, leaving only pallets that share no line with a survivor. The count of liftables is exactly the total minus the number of row/column-connected clutches that must each leave one behind.

Input: A list stones where stones[i] = [x, y] is the coordinate of a pallet; coordinates are unique.

Output: Return the maximum number of pallets that can be removed.

Constraints

1 <= stones.length <= 10^3
0 <= x, y <= 10^4
No two stones share a coordinate

Examples

Example 1

Input: {"stones":[[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]}
Output: 5
All six pallets form one connected clutch, so only one anchor must remain.

Example 2

Input: {"stones":[[0,0],[0,2],[1,1],[2,0],[2,2]]}
Output: 3
The four corner pallets chain by rows and columns; the centre pallet is on no shared line.

Solve this in your browser →

Also on LeetCode ↗