Most Stones Removed With Same Row Or Column - Leetcode Solution

The problem statement for the "Most Stones Removed With Same Row Or Column" problem on LeetCode is as follows:

You are given a 2D plane of stones, represented by a 2D array. Each element in the array is a pair of integers (i,j) representing the location of a stone at position (i,j). You want to remove as many stones as possible. The only restriction is that you cannot remove a stone if it shares a row or column with another stone that has not been removed.

Write a function to return the maximum number of stones you can remove.

To solve this problem, we can use the concept of disjoint sets.

We define a set for each stone where the set contains all the stones that are in the same row or column as that stone. We can use a dictionary to map each stone to its corresponding set.

We traverse through the stones one by one and if we find a stone (i,j) such that there is already a stone in the same row or column as (i,j), we merge the sets corresponding to both stones. We can use union-find algorithm to merge the sets efficiently.

After merging all the sets, the number of stones that can be removed will be equal to the total number of stones minus the number of disjoint sets.

Following is the Python code for the solution:

class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        parent = {}
        def find(x):
            if x != parent[x]:
                parent[x] = find(parent[x])
            return parent[x]
        def union(x,y):
            parent.setdefault(x,x)
            parent.setdefault(y,y)
            parent[find(x)] = find(y)
        
        for x,y in stones:
            union(x+10001, y)
        
        return len(stones)-len({find(x+10001) for x,y in stones})

In this code, we first define parent dictionary to hold the parent for each stone. We define two functions: find(x) which returns the root parent of a set and union(x,y) which merges the sets containing elements x and y.

We iterate through each stone in the input array and merge the sets of stones in the same row and column using union(x,y).

Finally, we return the total number of stones in the input array minus the number of disjoint sets using len(stones)-len({find(x+10001) for x,y in stones}). We add 10001 to each row index to differentiate between row and column indices as they can be equal.

This code has time complexity of O(N\alpha(N)) where N is the number of stones and \alpha is the Inverse-Ackermann function.

1