Solution For Most Stones Removed With Same Row Or Column

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.

Step by Step Implementation For Most Stones Removed With Same Row Or Column

There are a few different ways to approach this problem. One way would be to keep track of which stones have been removed and which are still remaining. Then, for each stone that is remaining, check to see if there are any other stones in the same row or column. If so, remove those stones as well. Repeat this process until there are no more stones remaining.

Another approach would be to keep track of which rows and columns have been visited. Then, for each stone that is remaining, check to see if the row or column has been visited. If not, visit the row or column and remove all of the stones. Repeat this process until there are no more stones remaining.

class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        # union find
        # for each stone, connect it with all stones with same row or column
        # return the number of connected components - 1
        
        # create a parent map to store the parent of each stone
        parent = {}
        
        # for each stone, connect it with all stones with same row or column
        for i, j in stones:
            # if the stone is not in the parent map, add it
            if (i, j) not in parent:
                parent[(i, j)] = (i, j)
            
            # for all other stones with same row as stone (i, j)
            for k in range(j + 1, len(stones[0])):
                # if the stone (i, k) is not in the parent map, add it
                if (i, k) not in parent:
                    parent[(i, k)] = (i, k)
                # connect stone (i, k) with stone (i, j)
                self.union((i, j), (i, k), parent)
            
            # for all other stones with same column as stone (i, j)
            for k in range(i + 1, len(stones)):
                # if the stone (k, j) is not in the parent map, add it
                if (k, j) not in parent:
                    parent[(k, j)] = (k, j)
                # connect stone (k, j) with stone (i, j)
                self.union((i, j), (k, j), parent)
        
        # return the number of connected components - 1
        return len(set(self.find(stone, parent) for stone in stones)) - 1
    
    # find the root of the given stone
    def find(self, stone, parent):
        # if the stone is its own parent, it is the root
        if parent[stone] == stone:
            return stone
        # otherwise, find the root of the parent of the stone
        return self.find(parent[stone], parent)
    
    # connect the given stones
    def union(self, stone1, stone2, parent):
        # find the roots of the two stones
        root1 = self.find(stone1, parent)
        root2 = self.find(stone2, parent)
        # connect the two roots
        parent[root2] = root1

var removeStones = function(stones) {
    // create a map to store the mapping of each stone's position to its connected stones
    let map = new Map();
    // loop through each stone
    for (let i = 0; i < stones.length; i++) {
        let stone = stones[i];
        // if the map doesn't have an entry for the stone's row, create one
        if (!map.has(stone[0])) {
            map.set(stone[0], new Set());
        }
        // if the map doesn't have an entry for the stone's column, create one
        if (!map.has(stone[1])) {
            map.set(stone[1], new Set());
        }
        // add the stone's position to its row and column entries in the map
        map.get(stone[0]).add(i);
        map.get(stone[1]).add(i);
    }
    // create a visited set to keep track of which stones have been visited
    let visited = new Set();
    // create a variable to store the number of connected components
    let numComponents = 0;
    // loop through each stone
    for (let i = 0; i < stones.length; i++) {
        // if the stone has not been visited
        if (!visited.has(i)) {
            // mark the stone as visited
            visited.add(i);
            // increment the number of connected components
            numComponents++;
            // create a queue to store the stones in the same connected component as the current stone
            let queue = [i];
            // while the queue is not empty
            while (queue.length > 0) {
                // get the next stone in the queue
                let stone = queue.shift();
                // get the row and column of the stone
                let row = stones[stone][0];
                let col = stones[stone][1];
                // get the stones connected to the stone's row
                let rowConnections = map.get(row);
                // get the stones connected to the stone's column
                let colConnections = map.get(col);
                // loop through the stones connected to the stone's row
                for (let j of rowConnections) {
                    // if the stone has not been visited
                    if (!visited.has(j)) {
                        // mark the stone as visited
                        visited.add(j);
                        // add the stone to the queue
                        queue.push(j);
                    }
                }
                // loop through the stones connected to the stone's column
                for (let j of colConnections) {
                    // if the stone has not been visited
                    if (!visited.has(j)) {
                        // mark the stone as visited
                        visited.add(j);
                        // add the stone to the queue
                        queue.push(j);
                    }
                }
            }
        }
    }
    // return the number of stones - the number of connected components (this will be the maximum number of stones that can be removed)
    return stones.length - numComponents;
};

//Solution:

int removeStones(vector>& stones) {
    int n = stones.size();
    
    //Create a graph with the stones as nodes
    //Connect nodes that are in the same row or column
    unordered_map> graph;
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            if(stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
                graph[i].insert(j);
                graph[j].insert(i);
            }
        }
    }
    
    //Do a DFS from each node to find connected components
    //The number of stones in each connected component - 1 is the number of moves needed to remove all stones in that component
    int res = 0;
    vector visited(n);
    for(int i = 0; i < n; i++) {
        if(!visited[i]) {
            int componentSize = 0;
            stack st;
            st.push(i);
            visited[i] = true;
            while(!st.empty()) {
                int curr = st.top();
                st.pop();
                componentSize++;
                for(int next : graph[curr]) {
                    if(!visited[next]) {
                        st.push(next);
                        visited[next] = true;
                    }
                }
            }
            res += componentSize - 1;
        }
    }
    
    return res;
}

using System; 
using System.Collections.Generic; 

public class Solution { 
    public int RemoveStones(int[][] stones) { 

// keep track of visited stones 
        HashSet visited = new HashSet(); 

// keep track of number of stones removed 
        int count = 0; 

// for each stone, check if it has been visited. 
// if not, remove all stones in the same row or column 
        for(int i = 0; i < stones.Length; i++) { 
            int[] stone = stones[i]; 
            if(!visited.Contains(stone)) { 
                RemoveStone(stone, stones, visited); 
                count++; 
            } 
        } 

// return number of stones removed 
        return stones.Length - count; 
    } 

// remove all stones in the same row or column as stone 
    public void RemoveStone(int[] stone, int[][] stones, HashSet visited) { 
        Queue queue = new Queue(); 
        queue.Enqueue(stone); 
        visited.Add(stone); 

// while queue is not empty 
        while(queue.Count != 0) { 
            int[] s = queue.Dequeue(); 

// for each stone in the same row or column as s 
            for(int i = 0; i < stones.Length; i++) { 
                int[] curr = stones[i]; 

// if curr has not been visited and is in the same row or column as s 
                if(!visited.Contains(curr) && (curr[0] == s[0] || curr[1] == s[1])) { 
// add curr to queue and mark as visited 
                    queue.Enqueue(curr); 
                    visited.Add(curr); 
                } 
            } 
        } 
    } 
}