Leetcode 984 Solution

This article provides solution to leetcode question 984 (most-stones-removed-with-same-row-or-column)
Categories:
Tags:
Access this page by simply typing in "lcs 984" in your browser address bar if you have bunnylol configured.

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

Solution

class FindUnionSet:
    def __init__(self, N):
        self.p = list(range(N))

    def find(self, i):
        if self.p[i] == i:
            return i

        self.p[i] = self.find(self.p[i])
        return self.p[i]

    def union(self, i, j):
        self.p[self.find(i)] = self.find(j)


class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        fuset = FindUnionSet(len(stones))

        ym = collections.defaultdict(list)
        xm = collections.defaultdict(list)
        for i, (s, d) in enumerate(stones):
            ym[s].append(i)
            xm[d].append(i)

        for indexes in list(ym.values()) + list(xm.values()):
            if len(indexes) < 2:
                continue

            for i in range(1, len(indexes)):
                fuset.union(indexes[0], indexes[i])

        counters = collections.defaultdict(int)
        for i in range(len(stones)):
            counters[fuset.find(i)] += 1

        ans = 0
        for counter in counters.values():
            ans += max(0, counter - 1)
        return ans