MediumNo. 0947
Most Stones Removed with Same Row or Column — LeetCode 947 Python Solution
- Pattern
- Union-Find
- Topics
- Depth-First Search, Union Find, Graph, Hash Table
- Reading time
- 6 min
- Source
- leetcode.com
The problem
On a 2D plane, we place n stones at some integer coordinate points. Each coordinate point may have at most one stone.
Example
- Input
- stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
- Output
- 5
- Explanation
- One way to remove 5 stones is as follows:
Python solution
class UnionFind:
def __init__(self, n):
self.p = list(range(n))
self.size = [1] * n
def find(self, x):
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, a, b):
pa, pb = self.find(a), self.find(b)
if pa == pb:
return False
if self.size[pa] > self.size[pb]:
self.p[pb] = pa
self.size[pa] += self.size[pb]
else:
self.p[pa] = pb
self.size[pb] += self.size[pa]
return True
class Solution:
def removeStones(self, stones: List[List[int]]) -> int:
uf = UnionFind(len(stones))
ans = 0
for i, (x1, y1) in enumerate(stones):
for j, (x2, y2) in enumerate(stones[:i]):
if x1 == x2 or y1 == y2:
ans += uf.union(i, j)
return ansComplexity
- Time
- O(n2 × α(n))
- Space · auxiliary
- O(n)
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 947. Most Stones Removed with Same Row or Column is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0924 | Minimize Malware Spread | Hard |
| 0928 | Minimize Malware Spread II | Hard |
| 2368 | Reachable Nodes With Restrictions | Medium |
| 0133 | Clone Graph | Medium |
| 0721 | Accounts Merge | Medium |
| 0839 | Similar String Groups | Hard |
Frequently asked questions
- How hard is LeetCode 947. Most Stones Removed with Same Row or Column?
LeetCode 947. Most Stones Removed with Same Row or Column is rated Medium on LeetCode.
- What is the time complexity of LeetCode 947. Most Stones Removed with Same Row or Column?
The Python solution on this page runs in O(n2 × α(n)).
- What is the space complexity of LeetCode 947. Most Stones Removed with Same Row or Column?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 947. Most Stones Removed with Same Row or Column cover?
LeetCode 947. Most Stones Removed with Same Row or Column is tagged Depth-First Search, Union Find, Graph and Hash Table on LeetCode.