LeetCode [947] Most Stones Removed with Same Row or Column

 947. Most Stones Removed with Same Row or Column

Medium

On a 2D plane, we place stones at some integer coordinate points.  Each coordinate point may have at most one stone.

Now, a move consists of removing a stone that shares a column or row with another stone on the grid.

What is the largest possible number of moves we can make?

 

Example 1:

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5

Example 2:

Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3

Example 3:

Input: stones = [[0,0]]
Output: 0

 

Note:

1. 1 <= stones.length <= 1000
2. 0 <= stones[i][j] < 10000

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

class Solution { int isLands = 0; Map<Integer, Integer> f = new HashMap<>(); public int removeStones(int[][] stones) { for(int[] s : stones){ if(!f.containsKey(s[0])){ f.put(s[0], s[0]); isLands ++; } if(!f.containsKey(~s[1])){ f.put(~s[1], ~s[1]); isLands ++; } } for(int[] s : stones){ union(s[0], ~s[1]); } return stones.length - isLands; } int find(int x){ if(x == f.get(x)) return x; else return find(f.get(x)); } void union(int x, int y){ x = find(x); y = find(y); if(x!=y){ isLands--; f.put(x, y); } } }