LeetCode 947. Most Stones Removed with Same Row or Column

Description

https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/

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

Explanation

Python Solution

class UnionFind:
    def __init__(self, N):
        self.p = [i for i in range(N)]
    
    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])

        return self.p[x]
    
    def union(self, x, y):
        xr = self.find(x)
        yr = self.find(y)
        self.p[xr] = yr
        
        
class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        n = len(stones)
        union_find = UnionFind(20000)
        
        for x, y in stones:
            union_find.union(x, y + 10000)
            
        return n - len({union_find.find(x) for x, y in stones})

• Time Complexity: ~N
• Space Complexity: ~d = log(N) to keep the recursion stack, where d is a tree depth.