Marc Lester Tan

This medium LC question is really difficult to solve if you don’t have any background about Disjoint Sets.

I had to look into other people’s solution to figure this out.

class Solution {
    fun removeStones(stones: Array<IntArray>): Int {        
        val dsu = DSU(20000)
        for(stone in stones){
            dsu.union(stone[0], stone[1]+10000)
        }
        
        val seen = mutableSetOf<Int>()
        
        for(stone in stones){
            seen.add(dsu.find(stone[0]))
        }
        
        return stones.size - seen.size
    }
    
    class DSU(n: Int) {
        private var parent = IntArray(n)
        
        init {
            for(i in 0 until n){
                parent[i] = i
            }
        }
        
        fun find(x: Int): Int {
            if(parent[x] != x) parent[x] = find(parent[x])
            return parent[x]
        }
        
        fun union(x: Int, y: Int){
            parent[find(x)] = find(y)
        }
    }
}

Runtime: 204 ms, faster than 100.00% of Kotlin online submissions for Most Stones Removed with Same Row or Column.
Memory Usage: 36.1 MB, less than 100.00% of Kotlin online submissions for Most Stones Removed with Same Row or Column.