365. Most stones removed with same row or column
There are n stones at integer coordinate points on a 2D plane, with at most one stone per coordinate point. Some stones need to be removed.A stone can be removed if it shares the same row or the same column as another stone that has not been removed.
Given an array of stones of length n where stones[i] = [xi, yi] represents the location of the ith stone, return the maximum possible number of stones that can be removed.
Example 1:
Input : n=6, stones = [[0, 0],[ 0, 1], [1, 0],[1, 2],[2, 1],[2, 2]]
Output: 5
Explanation: One of the many ways to remove 5 stones is to remove the following stones:
[0,0], [1,0], [0,1], [2,1], [1,2]
Example 2:
Input : n = 6, stones = [[0, 0], [0, 2], [1, 3], [3, 1], [3, 2], [4, 3]]
Output: 4
Explanation: We can remove the following stones: [0,0], [0,2], [1,3], [3,1]
Now Your Turn!
Pick the correct output for the given inputInput: n = 2, stones = [[0, 0], [0, 2]]
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- 1 <= n <=1000
- 0 <= x[i], y[i]<= 104
- No two stones are at same position.