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(n^2 \times \alpha(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.

Most Stones Removed with Same Row or Column — LeetCode 947 Python Solution

MediumDepth-First SearchUnion FindGraphHash Table

Problem: #947
Pattern: Union-Find
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

Python

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 ans

Complexity

Measure	Complexity
Time	O(n^2 \times \alpha(n))
Space	O(n) auxiliary

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.

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(n^2 \times \alpha(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.