Problem statement

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

Solution 1

First solution is using idea of union find: we connect two stones if they have equal coordinate x or equal coordinate y. What is problem actually asking is number of connected components. We create graph with nodes: columns and rows (x1, ..., xn, y1, ..., yn), where we say two nodes are connected if we have stone in the intersection of column and row (that is graph is bipartitie). We can decode comumns by shift by N, with big enough value. Then when we run

for i, j in stones: dsu.union(i, j + N)

in this line we add N edges to our graph. Finally we just check number of components.

Complexity

It is O(n) if we use DSU with ranks and path compressions.

Code

class DSU:
    def __init__(self, graph):
        self.p = {i:i for i in graph}

    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):
        self.p[self.find(x)] = self.find(y)

class Solution:
    def removeStones(self, stones):
        N = 10000
        graph = [i for i, j in stones] + [j + N for i, j in stones]
        dsu = DSU(graph)
        for i, j in stones: dsu.union(i, j + N)
        groups = set(dsu.find(el) for el in graph)
        return len(stones) - len(groups)

Solution 2

We can solve this with dfs as well. We have two types of nodes: for every column create all possible connections for this column , same for row. In fact, no need to create all connections, we can only add connection between adjacent nodes in each column (and row). Like (1, 1) - (3, 1) - (5, 1) - (10, 1) for the second one and full 4-element graph for the first one. Not neccecarily sort each row\column, in this way we will have truly linear complexity: if we connect (1, 1) -> (10, 1) -> (3, 1) -> (5, 1) then components are still the same.

Complexity

Time and space complexity is O(n).

Code

class Solution:
    def removeStones(self, stones):
        def dfs(q):
            visited.add(q)
            for neib in graph[q]:
                if neib not in visited: dfs(neib)
            
        rows, cols = defaultdict(list), defaultdict(list)
        graph, visited, ans = defaultdict(list), set(), 0
        
        for i, j in stones:
            rows[i].append(j)
            cols[j].append(i)
            
        for r, k in rows.items():
            for i, j in zip(k, k[1:]):
                graph[r, i].append((r, j))
                graph[r, j].append((r, i))
        
        for c, k in cols.items():
            for i, j in zip(k, k[1:]):
                graph[i, c].append((j, c))
                graph[j, c].append((i, c))
                
        for i, j in stones:
            if (i, j) not in visited:
                dfs((i, j))
                ans += 1
                
        return len(stones) - ans