> ## Content Index
> Fetch the complete content index at: https://andybase.com/llms.txt
> Use this file to discover other available public pages before exploring further.

# 947	 Most Stones Removed with Same Row or Column
- URL: https://andybase.com/947-most-stones-removed-with-same-row-or-column/
- Published: 2018-11-26T20:52:43.000Z
- Updated: 2018-11-26T20:52:43.000Z
- Author: andy
- Tags: leetcode, contest, #Migrated-1784083136856, #wp, #wp-post, #Import 2026-07-15 02:38

Link: [Most Stones Removed with Same Row or Column](https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/?ref=andybase.com)

## Thought

When I saw the question, I realized its a Union Find question - For any union, I can keep only one stone form it. Then it convert to a count how many unique union finds exist question. 

So, only need to count all unique union find, and use all nodes to minus it. 

## Code

```
class Solution:
    def removeStones(self, stones):
        """
        :type stones: List[List[int]]
        :rtype: int
        """
        N = len(stones)
        nodes = dict()
        cols = collections.defaultdict(set)
        rows = collections.defaultdict(set)
        counter = set()
        for x, y in stones: # pre process
            nodes[(x,y)] = (x,y)
            cols[x].add(y)
            rows[y].add(x)
        def find(x,y):
            if nodes[(x,y)]!= (x,y):
                nx,ny = find(*nodes[(x,y)])
                nodes[(x,y)] = (nx,ny)
            return nodes[(x,y)]
        def union(x,y,x2,y2):
            n_x , n_y = find(x,y)
            nn_x, nn_y = find(x2,y2)
            nodes[(nn_x,nn_y)] = (n_x, n_y)
        for x, y in stones:
            for y2 in cols[x]:
                union(x,y,x,y2)
            for x2 in rows[y]:
                union(x,y, x2,y)
        maxx = 0
        for x,y in stones:
            r_x, r_y = find(x,y)
            counter.add((r_x,r_y))
        return N - len(counter) 
```

## Runtime

Time: O(n^2)

Space: O(n)