#947

Medium

auto_awesomeGraph traversal with depth-first search

LeetCode Problem Workspace

Most Stones Removed with Same Row or Column

Maximize the number of stones removed from a 2D plane using graph traversal and DFS.

hash table depth first search union find graph

Problem Statement

You are given a 2D plane with n stones, each at a unique integer coordinate point. A stone can be removed if it shares either the same row or column with another stone that remains on the plane. The task is to find the maximum number of stones that can be removed while following these constraints.

You are given an array of stones where stones[i] = [xi, yi] represents the coordinate of the ith stone. Your goal is to return the largest number of stones that can be removed while adhering to the rule of removal, ensuring that no two stones are removed simultaneously if they don’t share a row or column.

Examples

Example 1

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]

Output: 5

One way to remove 5 stones is as follows:

Remove stone [2,2] because it shares the same row as [2,1].
Remove stone [2,1] because it shares the same column as [0,1].
Remove stone [1,2] because it shares the same row as [1,0].
Remove stone [1,0] because it shares the same column as [0,0].
Remove stone [0,1] because it shares the same row as [0,0]. Stone [0,0] cannot be removed since it does not share a row/column with another stone still on the plane.

Example 2

Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]

Output: 3

One way to make 3 moves is as follows:

Remove stone [2,2] because it shares the same row as [2,0].
Remove stone [2,0] because it shares the same column as [0,0].
Remove stone [0,2] because it shares the same row as [0,0]. Stones [0,0] and [1,1] cannot be removed since they do not share a row/column with another stone still on the plane.

Example 3

Input: stones = [[0,0]]

Output: 0

[0,0] is the only stone on the plane, so you cannot remove it.

Constraints

1 <= stones.length <= 1000
0 <= xi, yi <= 104
No two stones are at the same coordinate point.

Solution Approach

Graph Representation

Represent each stone as a node in a graph, with edges between stones that share the same row or column. This approach allows you to treat the stones as connected components, where each component can be removed by removing one stone from it.

Depth-First Search (DFS)

Use DFS to explore the graph and find the connected components. Starting from any unvisited stone, traverse all connected stones, marking them as visited. For each connected component, you can remove all but one stone.

Union-Find Data Structure

Use the Union-Find data structure to efficiently group stones that share the same row or column. This approach allows for quick union and find operations, which is essential for solving the problem in linear time.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n + 20002)

The time complexity is O(n) because each stone is visited once during the DFS or Union-Find operations. The space complexity is O(n + 20002) due to the storage required for the stones' coordinates and the extra space needed for Union-Find parent pointers.

What Interviewers Usually Probe

Focus on graph traversal patterns to explore the problem space.
Test the candidate's understanding of DFS and its application in a graph traversal problem.
Look for efficiency in using Union-Find to handle large inputs with minimal time complexity.

Common Pitfalls or Variants

Common pitfalls

Failing to optimize the search process and running into time limit errors with larger inputs.
Overcomplicating the graph representation, leading to unnecessary space usage or slower performance.
Not handling edge cases like when there’s only one stone, which cannot be removed.

Follow-up variants

Consider problems where the stones can be removed in a different pattern, such as only removing stones from the same row or same column at once.
Explore the problem with varying input sizes to test performance and scalability.
Change the problem such that stones can be removed if they are in the same diagonal, testing how candidates adapt their graph traversal logic.

FAQ

How does DFS help in solving the 'Most Stones Removed with Same Row or Column' problem?

DFS helps by allowing you to explore all connected stones from a given starting point, efficiently identifying connected components that can be removed in one go.

What is the best way to optimize stone removals in this problem?

The best approach is to use graph traversal, specifically DFS or Union-Find, to efficiently group stones that can be removed together.

What makes this problem a good candidate for using Union-Find?

Union-Find is ideal for this problem because it helps efficiently manage the connectivity between stones, supporting fast union and find operations to identify groups of removable stones.

Can stones be removed if they only share a diagonal?

No, stones can only be removed if they share the same row or column. Diagonal connections are not considered for removals.

How does the problem scale with increasing stone count?

The problem scales efficiently with the use of DFS or Union-Find, both of which work within linear time complexity, ensuring fast performance even with the upper limit of 1000 stones.

terminal

Solution

Solution 1: Union-Find

We can use a union-find data structure to maintain the relationships between stones. If two stones are in the same row or column, we consider them to be connected and use the union-find to link them together. In the end, we count how many connected components there are in the union-find, which corresponds to the number of stones that can remain. Therefore, the total number of stones that can be removed is the total number of stones minus the number of stones that can remain. We can also record the number of successful unions during the merge process, which equals the number of stones that can be removed.

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

Solution 2: Union-Find (Optimized)

We can add an offset to the y-coordinates of the stones, allowing us to unify the x-coordinates and y-coordinates. Then, we use a union-find data structure to maintain the relationship between x-coordinates and y-coordinates.

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

Solution 3: DFS

#### TypeScript

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

Continue Practicing

#928 minimize malware spread ii #924 minimize malware spread #959 regions cut by slashes