Most Stones Removed with Same Row or Column

Leetcode Problem:

• Most Stones Removed with Same Row or Column

Summary

• Given a 2D plane with n stones, remove the maximum number of stones that can be removed if a stone can be removed if it shares either the same row or the same column as another stone that has not been removed.

Approach

• Use a union-find data structure to group stones that share the same row or column
• Then, count the number of connected components to determine the maximum number of stones that can be removed.

Complexity

• O(n + m) where n is the number of stones and m is the maximum column or row value

Explain

• Create two maps to store the columns and rows of each stone
• Then, iterate over each stone and add its column and row to the corresponding maps
• After that, create a visited array to keep track of the stones that have been visited
• Then, iterate over each stone and use a helper function to mark all the stones in the same row or column as visited
• Finally, count the number of connected components in the visited array to determine the maximum number of stones that can be removed.

Solution Code:

class Solution {
public:
    vector cols[10000];
    vector rows[10000];
    bool visited[1000];
    map getIdx;
    void fill(int r, int c){
        int idx = getIdx[r*10000+c];
        if (visited[idx]) return;
        visited[idx] = true;
        for(int i = 0 ; i < cols[r].size(); i++){
            fill(r, cols[r][i]);
        }
        for(int i = 0 ; i < rows[c].size(); i++){
            fill(rows[c][i], c);
        }
    }
    int removeStones(vector>& stones) {
        for(int i = 0 ; i < stones.size(); i++){
            int r = stones[i][0];
            int c = stones[i][1];
            cols[r].push_back(c);
            rows[c].push_back(r);
            getIdx[r*10000+c] = i;
        }
        int uni = 0;
        for(int i = 0 ; i < stones.size(); i++){
            if(visited[i]) continue;
            uni++;
            fill(stones[i][0], stones[i][1]);
        }
        return stones.size() - uni;
    }
};