947. Most Stones Removed with Same Row or Column

  • Hardness: \(\color{orange}\textsf{Medium}\)
  • Ralated Topics: Depth-First Search、Union Find、Graph

一、題目

On a 2D plane, we place n stones at some integer coordinate points. Each coordinate point may have at most one stone. A stone can be removed if it shares either the same row or the same column as another stone that has not been removed. Given an array stones of length n where stones[i] = [xi, yi] represents the location of the ith stone, return the largest possible number of stones that can be removed.

Example 1:

  • Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
  • Output: 5
  • Explanation: One way to remove 5 stones is as follows:
  1. Remove stone [2,2] because it shares the same row as [2,1].
  2. Remove stone [2,1] because it shares the same column as [0,1].
  3. Remove stone [1,2] because it shares the same row as [1,0].
  4. Remove stone [1,0] because it shares the same column as [0,0].
  5. 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
  • Explanation: One way to make 3 moves is as follows:
  1. Remove stone [2,2] because it shares the same row as [2,0].
  2. Remove stone [2,0] because it shares the same column as [0,0].
  3. 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
  • Explanation: [0,0] is the only stone on the plane, so you cannot remove it.

Constraints:

  • 1 <= stones.length <= 1000
  • 0 <= xi, yi <= 10^4
  • No two stones are at the same coordinate point.

二、分析

  • 典型的圖論問題，若兩個 stone 的 x 座標與 y 座標有一者相等，則可以看作它們之間有一條邊。
  • 所有以邊相連的 stone，最後可以移除到剩下最後一個 stone。
  • 可以移除的 stone 的最大值為所有 stone 數量減去留下的 stone 的數量。

三、解題

1. DFS

  • Time complexity: \(O(n^2)\)
  • Space complexity: \(O(n)\)
void dfs(vector<vector<int>>& stones, vector<bool>& vis, int i) {
    vis[i] = true;                              // 記錄拜訪
    int r1 = stones[i][0], c1 = stones[i][1];
    for (int j = 0; j < stones.size(); j++) {
        if (vis[j]) continue;
        int r2 = stones[j][0], c2 = stones[j][1];
        if (r1 == r2 || c1 == c2) {             // 有 x 軸或 y 軸相同
            dfs(stones, vis, j);
        }
    }
}
int removeStones(vector<vector<int>>& stones) {
    vector<bool> vis(stones.size(), false);     // 用來記錄拜訪過了沒
    int cnt = 0;                                // 可以留下來的石頭個數
    for (int i = 0; i < stones.size(); i++) {
        if (vis[i]) continue;                   // 拜訪過則跳過
        cnt++;
        dfs(stones, vis, i);                    // 將相連的石頭都拜訪過一遍
    }
    return stones.size() - cnt;
}

2. Union Find

  • Time complexity: \(O(n\log n)\)
  • Space complexity: \(O(n)\)
class UF {
private:
    unordered_map<int,int> parent;
    int cnt = 0;
public:
    UF () {}
    int size() {
        return cnt;
    }
    int find(int x) {
        if (!parent.count(x)) {
            parent[x] = x;
            cnt++;
        }
        if (x != parent[x]) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    void connect(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return;
        parent[rootX] = rootY;
        cnt--;
    }
};
class Solution {
public:
    int removeStones(vector<vector<int>>& stones) {
        int n = stones.size();
        UF uf;
        for (auto stone : stones) {
            uf.connect(stone[0] + 10001, stone[1]);
        }
        return n - uf.size();
    }
};

回目錄 Catalog