Formatted question description: https://leetcode.ca/all/947.html

947. Most Stones Removed with Same Row or Column (Medium)

On a 2D plane, we place stones at some integer coordinate points.  Each coordinate point may have at most one stone.

Now, a move consists of removing a stone that shares a column or row with another stone on the grid.

What is the largest possible number of moves we can make?

 

Example 1:

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5

Example 2:

Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3

Example 3:

Input: stones = [[0,0]]
Output: 0

 

Note:

  1. 1 <= stones.length <= 1000
  2. 0 <= stones[i][j] < 10000

Related Topics:
Depth-first Search, Union Find

Solution 1. DFS Iterative

Let’s call stone A and B are neighbors if they are in the same row/column.

Define a component as a set of stones where each of them are neighbors and none of them is neighbor of stones outside of this set.

For each component, we can always remove the stones until there is just one left.

So we use DFS to visit the stones in the same component, and each component can contribute conponentSize - 1 moves.

// OJ: https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/

// Time: O(N^2)
// Space: O(N^2)
// Ref: https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/solution/
class Solution {
public:
    int removeStones(vector<vector<int>>& stones) {
        int N = stones.size();
        vector<vector<int>> graph(N, vector<int>(N));
        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][++graph[i][0]] = j;
                    graph[j][++graph[j][0]] = i;
                }
            }
        }
        int ans = 0;
        vector<bool> seen(N);
        for (int i = 0; i < N; ++i) {
            if (seen[i]) continue;
            stack<int> s;
            s.push(i);
            seen[i] = true;
            --ans;
            while (s.size()) {
                int node = s.top();
                s.pop();
                ++ans;
                for (int j = 1; j <= graph[node][0]; ++j) {
                    int n = graph[node][j];
                    if (!seen[n]) {
                        s.push(n);
                        seen[n] = true;
                    }
                }
            }
        }
        return ans;
    }
};

Solution 2. DFS Recursive

// OJ: https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/

// Time: O(N^2)
// Space: O(N^2)
class Solution {
    void dfs(vector<vector<int>> &G, vector<bool> &visited, int start) {
        visited[start] = true;
        for (int n : G[start]) {
            if (visited[n]) continue;
            dfs(G, visited, n);
        }
    }
    int getComponentCount(vector<vector<int>> &G) {
        vector<bool> visited(G.size());
        int ans = 0;
        for (int i = 0; i < G.size(); ++i) {
            if (visited[i]) continue;
            ++ans;
            dfs(G, visited, i);
        }
        return ans;
    }
public:
    int removeStones(vector<vector<int>>& stones) {
        int N = stones.size();
        vector<vector<int>> G(N);
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
                    G[i].push_back(j);
                    G[j].push_back(i);
                }
            }
        }
        return stones.size() - getComponentCount(G);
    }
};

Solution 3. BFS

// OJ: https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/

// Time: O(N^2)
// Space: O(N^2)
class Solution {
    void bfs(vector<vector<int>> &G, vector<bool> &visited, int start) {
        visited[start] = true;
        queue<int> q;
        q.push(start);
        while (q.size()) {
            int u = q.front();
            q.pop();
            for (int v : G[u]) {
                if (visited[v]) continue;
                visited[v] = true;
                q.push(v);
            }
        }
    }
    int getComponentCount(vector<vector<int>> &G) {
        int ans = 0;
        vector<bool> visited(G.size());
        for (int i = 0; i < G.size(); ++i) {
            if (visited[i]) continue;
            ++ans;
            bfs(G, visited, i);
        }
        return ans;
    }
public:
    int removeStones(vector<vector<int>>& stones) {
        int N = stones.size();
        vector<vector<int>> G(N);
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
                    G[i].push_back(j);
                    G[j].push_back(i);
                }
            }
        }
        return stones.size() - getComponentCount(G);
    }
};

Solution 4. Union Find

// OJ: https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/

// Time: O(N^2)
// Space: O(N)
class UnionFind {
    vector<int> id, rank;
    int cnt;
public:
    UnionFind(int n) : cnt(n), id(n), rank(n, 1) {
        for (int i = 0; i < n; ++i) id[i] = i;
    }
    int find(int a) {
        return id[a] == a ? a : (id[a] = find(id[a]));
    }
    void connect(int a, int b) {
        int x = find(a), y = find(b);
        if (x == y) return;
        if (rank[x] <= rank[y]) {
            id[x] = y;
            if (rank[x] == rank[y]) rank[y]++;
        } else id[y] = x;
        --cnt;
    }
    int getCount() { return cnt; }
};
class Solution {
public:
    int removeStones(vector<vector<int>>& stones) {
        int N = stones.size();
        UnionFind uf(N);
        for (int i = 0; i < N; ++i) {
            for (int j = i; j < N; ++j) {
                if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
                    uf.connect(i, j);
                }
            }
        }
        return stones.size() - uf.getCount();
    }
};

Java

class Solution {
    public int removeStones(int[][] stones) {
        int length = stones.length;
        if (length <= 1)
            return 0;
        int[] parents = new int[20000];
        for (int i = 0; i < 20000; i++)
            parents[i] = i;
        for (int[] stone : stones)
            union(parents, stone[0], stone[1] + 10000);
        Set<Integer> set = new HashSet<Integer>();
        for (int[] stone : stones)
            set.add(findAncestor(parents, stone[0]));
        return length - set.size();

    }

    public void union(int[] parents, int row, int column) {
        int rowParent = findAncestor(parents, row), columnParent = findAncestor(parents, column);
        if (rowParent != columnParent)
            parents[rowParent] = columnParent;
    }

    public int findAncestor(int[] parents, int start) {
        int ancestor = start;
        int cur = start;
        while (ancestor != parents[ancestor])
            ancestor = parents[ancestor];
        while (cur != parents[cur]) {
            int curParent = parents[cur];
            parents[cur] = ancestor;
            cur = curParent;
        }
        return ancestor;
    }
}

All Problems

All Solutions