---
tags: leetcode
---

# [947. Most Stones Removed with Same Row or Column](https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/)
---
# My Solution
## Solution 1: DFS
### The Key Idea for Solving This Coding Question
### C++ Code 1

class Solution {
public:
    int removeStones(vector<vector<int>> &stones) {
        unordered_map<int, vector<int>> xGraph, yGraph;
        for (int i = 0; i < stones.size(); ++i) {
            int x = stones[i][0], y = stones[i][1];
            
            xGraph[x].push_back(i);
            yGraph[y].push_back(i);
        }
        
        int cmpCnt = 0;
        vector<bool> visited(stones.size(), false);
        for (int i = 0; i < stones.size(); ++i) {
            if (!visited[i]) {
                dfs(stones, xGraph, yGraph, visited, i);
                ++cmpCnt;
            }
        }
        
        return stones.size() - cmpCnt;
    }

private:
    void dfs(vector<vector<int>> &stones, 
             unordered_map<int, vector<int>> &xGraph, 
             unordered_map<int, vector<int>> &yGraph,
             vector<bool> &visited, 
             int curr) {
        visited[curr] = true;
        
        for (auto &next : xGraph[stones[curr][0]]) {
            if (visited[next]) {
                continue;
            }
            dfs(stones, xGraph, yGraph, visited, next);
        }
        
        for (auto &next : yGraph[stones[curr][1]]) {
            if (visited[next]) {
                continue;
            }
            dfs(stones, xGraph, yGraph, visited, next);
        }
    }
};

#### Time Complexity
$O(N + E)$
* $N$ is the length of `stones`.
* $E$ is the number of edges in the graph.
#### Space Complexity
$O(N + E)$
### C++ Code 2

class Solution {
public:
    int removeStones(vector<vector<int>> &stones) {
        unordered_map<int, vector<int>> graph;
        for (int i = 0; i + 1 < stones.size(); ++i) {
            for (int j = i + 1; j < stones.size(); ++j) {
                if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
                    graph[i].push_back(j);
                    graph[j].push_back(i);
                }
            }
        }

        int numOfGroups = 0;
        vector<bool> visited(stones.size(), false);
        for (int i = 0; i < stones.size(); ++i) {
            if (!visited[i]) {
                dfs(graph, visited, i);
                ++numOfGroups;
            }
            
        }

        return stones.size() - numOfGroups;
    }

private:
    void dfs(unordered_map<int, vector<int>> &graph, vector<bool> &visited, int curr) {
        visited[curr] = true;

        for (auto &next : graph[curr]) {
            if (visited[next]) {
                continue;
            }
            dfs(graph, visited, next);
        }
    }
};

#### Time Complexity
$O(N^{2} + E)$
* $N$ is the length of `stones`.
* $E$ is the number of edges in the graph.
#### Space Complexity
$O(N + E)$
## Solution 2: BFS
### The Key Idea for Solving This Coding Question
### C++ Code

class Solution {
public:
    int removeStones(vector<vector<int>> &stones) {
        unordered_map<int, vector<int>> graph;
        for (int i = 0; i + 1 < stones.size(); ++i) {
            for (int j = i + 1; j < stones.size(); ++j) {
                if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
                    graph[i].push_back(j);
                    graph[j].push_back(i);
                }
            }
        }

        int numOfGroups = 0;
        vector<bool> visited(stones.size(), false);
        for (int i = 0; i < stones.size(); ++i) {
            if (!visited[i]) {
                bfs(graph, visited, i);
                ++numOfGroups;
            }
            
        }

        return stones.size() - numOfGroups;
    }

private:
    void bfs(unordered_map<int, vector<int>> &graph, vector<bool> &visited, int start) {
        queue<int> q;

        q.push(start);
        visited[start] = true;
        while (!q.empty()) {
            int curr = q.front();
            q.pop();

            for (auto &next : graph[curr]) {
                if (visited[next]) {
                    continue;
                }
                q.push(next);
                visited[next] = true;
            }
        }
        
    }
};

### Time Complexity
$O(N + E)$
* $N$ is the length of `stones`.
* $E$ is the number of edges in the graph.
### Space Complexity
$O(N + E)$
## Solution 3: Union Find
### The Key Idea for Solving This Coding Question
### C++ Code

class unionFind {
private:
    unordered_map<int, int> parent;
    unordered_map<int, int> rank;
    int numComps;
    
public:
    unionFind(vector<vector<int>>& stones) {
        for (vector<int>& stone : stones) {
            int r = stone[0] + 20000;
            int c = stone[1];
            parent[r] = r;
            parent[c] = c;
        }
        
        numComps = parent.size();
    }
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    void unify(int x, int y) {
        int setX = find(x);
        int setY = find(y);
        
        if (setX == setY) {
            return;
        }
        
        --numComps;
        if (rank[setX] < rank[setY]) {
            parent[setX] = setY;
        } else if (rank[setY] < rank[setX]) {
            parent[setY] = setX;
        } else {
            parent[setY] = setX;
            ++rank[setX];
        }
    }
    
    int getNumComps() {
        return numComps;
    }
};

class Solution {
public:
    int removeStones(vector<vector<int>>& stones) {
        unionFind uf(stones);
        for (vector<int>& stone : stones) {
            int r = stone[0] + 20000;
            int c = stone[1];
            uf.unify(r, c);
        } // end of for-range
        
        return stones.size() - uf.getNumComps();
    }
};

### Time Complexity
$O(n)$
* $n$ is the length of `stones`.
### Space Complexity
$O(n)$
* $n$ is the length of `stones`.
# Miscellaneous
<!--
# Test Cases

[[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]

[[0,0],[0,2],[1,1],[2,0],[2,2]]

[[0,0]]

* Wrong Answer:

[[0,1],[1,2],[1,3],[3,3],[2,3],[0,2]]

* Wrong Answer:
https://leetcode.com/submissions/detail/541836968/testcase
-->