Most Stones Removed with Same Row or Column
On a 2D plane, we place n stones at some integer coordinate points. Each coordinate point may have at most one stone.
A stone can be removed if it shares either the same row or the same column as another stone that has not been removed.
Given an array stones of length n where stones[i] = [xi, yi] represents the location of the i^th stone, return the largest possible number of stones that can be removed.
Example 1
Input
stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]Output
5Five stones can be removed in sequence, leaving only
[0,0], which no longer shares a row or column with another remaining stone.Example 2
Input
stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]Output
3Three stones can be removed, after which the remaining stones
[0,0] and [1,1] do not share a row or column with another stone still on the plane.Constraints
- 1 <= stones.length <= 1000
- 0 <= xi, yi <= 10^4
- No two stones are at the same coordinate point.