diff options
Diffstat (limited to 'most_stones_remove.py')
-rw-r--r-- | most_stones_remove.py | 34 |
1 files changed, 34 insertions, 0 deletions
diff --git a/most_stones_remove.py b/most_stones_remove.py new file mode 100644 index 0000000..1f12d3e --- /dev/null +++ b/most_stones_remove.py @@ -0,0 +1,34 @@ +# 947. Most Stones Removed with Same Row or Column + +""" +on a 2d plane, we place 'n' stones at some integer coordinate stones. 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] = [x_i, +y_i]' represents the location of the i'th stone, return the largest possible +number of stones that can be removed +""" + + +class Solution(object): + def removeStones(self, stones): + """ + :type stones: List[List[int]] + :rtype: int + """ + uf = {} + + def find(x): + if x != uf.setdefault(x, x): + uf[x] = find(uf[x]) + return uf[x] + + for i, j in stones: + uf[find(i)] = find(~j) + return len(stones) - len({find(x) for x in uf}) + + +if __name__ == "__main__": + obj = Solution() + print(obj.removeStones(stones=[[0, 0], [0, 1], [1, 0], [1, 2], [2, 1], [2, 2]])) + print(obj.removeStones(stones=[[0, 0], [0, 2], [1, 1], [2, 0], [2, 2]])) |