Leetcode Daily Question 29/08/2024 - 947. Most Stones Removed with Same Row or Column

Problem Description:

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 ith stone, return the largest possible number of stones that can be removed.

class UnionFind:
  def __init__(self):
    self.parent = {}
    
  def find(self, x):
    if self.parent.setdefault(x, x) != x:
      self.parent[x] = self.find(self.parent[x])
    return self.parent[x]
  
  def union(self, x, y):
    rootX = self.find(x)
    rootY = self.find(y)
    if rootX != rootY:
      self.parent[rootX] = rootY
      
      
from typing import List
class Solution:
  def removeStones(self, stones: List[List[int]]):
    uf = UnionFind()
    
    for x, y in stones:
      uf.union(x, ~y)
    
    return len(stones) - len({uf.find(x) for x, y in stones})

Explanation:

We can use union-find to solve this problem. Since we can reduce each disjoint set into just 1 stone, we "find" that the max number of stones that can be removed must equal to the the number of stones minus the number of unique sets.

To define the UnionFind class we define a set to store the parents of the disjoint sets.

The find function finds the root of each node(stone). We also compresses the paths, so that every child points directly to the parent, instead of having intermediates.

The union function group all the disjoint sets together by setting the root of one set as the parent of the other.

class UnionFind:
  def __init__(self):
    self.parent = {}
  
  def find(self, x):
    if self.parent.setdefault(x, x) != x:
      self.parent[x] = self.find(self.parent[x]) #path compression
    return self.parent[x] 
  
  def union(self, x, y):
    rootX = self.find(x)
    rootY = self.find(y)
    if rootX != rootY:
      self.parent[rootX] = rootY

For the main function, we simply initiate the union find object for the stones. Note that to avoid collision of indices, we would negate the value of column using the bitwise operator '~'.

def removeStones(stones):
  uf = UnionFind() #initiate union find object
  for x, y in stones:
    uf.union(x, ~y)
    
  return len(stones) - len({uf.find(x) for x, y in stones})

The time complexity is O(n). The union find operations have time complexity O(a(n)) where a(n) is the inverse Ackermann function. This is approximately O(1). We need to visit every stone to perform these operations, so thats O(n).

The space complexity is O(n). Since we need to store the unique roots and the parents, which have worst case of O(2n) and O(n) respectively.

The full solution can be found near the top of the page.