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

Analysis & Solution

关键思路在于转化问题为Number of Islands：

每次移除的stone必须是一个属于connected component（也就是一个island）中的坐标，那么最后剩余的，就将是每个island都最后一个点。因此总的可以移除的stone数目：number os stones to be removed = total number of stones - number of islands

Union Find 并查集

HashMap implementation of Union Find

966 ms, faster than 0.98%

class Solution {
    public static int numberOfIslands;
    public static HashMap<String, String> parent;

    private String buildKey(int[] coordinate) {
        return coordinate[0] + "," + coordinate[1];
    }

    public int removeStones(int[][] stones) {
        numberOfIslands = stones.length;
        parent = new HashMap<>();
        for (int[] stone: stones) {
            String s = buildKey(stone);
            parent.put(s, s);
        }

        for (int[] s1: stones) {
            String key1 = buildKey(s1);
            for (int[] s2: stones) {
                String key2 = buildKey(s2);
                if (s1[0] == s2[0] || s1[1] == s2[1]) {
                    union(key1, key2);
                }
            }
        }
        return stones.length - numberOfIslands;
    }

    private String find(String key) {
        if (!parent.get(key).equals(key)) {
            parent.put(key, find(parent.get(key)));
        }
        return parent.get(key);
    }
    private void union(String k1, String k2) {
        String p1 = find(k1);
        String p2 = find(k2);
        if (!p1.equals(p2)) {
            parent.put(p1, p2);
            numberOfIslands--;
        }
    }
}

Array Implementation of Union Find

class Solution {
    public int removeStones(int[][] stones) {
        int N = stones.length;
        DSU dsu = new DSU(20000);

        for (int[] stone: stones)
            dsu.union(stone[0], stone[1] + 10000);

        Set<Integer> seen = new HashSet();
        for (int[] stone: stones)
            seen.add(dsu.find(stone[0]));

        return N - seen.size();
    }
}

class DSU {
    int[] parent;
    public DSU(int N) {
        parent = new int[N];
        for (int i = 0; i < N; ++i)
            parent[i] = i;
    }
    public int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    public void union(int x, int y) {
        parent[find(x)] = find(y);
    }
}

• Time Complexity: O(NlogN), where N is the length of stones. (If we used union-by-rank, this can be O(N∗α(N)), where α is the Inverse-Ackermann function.)

• Space Complexity: O(N).

DFS

Recursive Implementation

class Solution {
    public int removeStones(int[][] stones) {
        int islands = 0;

        Set<Integer> visited = new HashSet<>();        

        for (int i = 0; i < stones.length; i++) {
            if (visited.contains(i)) continue;
            islands++;
            dfs(i, stones, visited);
        }

        return stones.length - islands;
    }

    private void dfs(int idx, int[][] stones, Set<Integer> visited) {
        visited.add(idx);

        for (int nextIdx = 0; nextIdx < stones.length; nextIdx++) {
            if (visited.contains(nextIdx)) continue;
            if (stones[idx][0] == stones[nextIdx][0] ||
                stones[idx][1] == stones[nextIdx][1]) {
                dfs(nextIdx, stones, visited);
            }
        }
    }
}

Stack Implementation

class Solution {
    public int removeStones(int[][] stones) {
        int N = stones.length;

        // graph[i][0] = the length of the 'list' graph[i][1:]
        int[][] graph = new int[N][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;
        boolean[] seen = new boolean[N];
        for (int i = 0; i < N; ++i) if (!seen[i]) {
            Stack<Integer> stack = new Stack();
            stack.push(i);
            seen[i] = true;
            ans--;
            while (!stack.isEmpty()) {
                int node = stack.pop();
                ans++;
                for (int k = 1; k <= graph[node][0]; ++k) {
                    int nei = graph[node][k];
                    if (!seen[nei]) {
                        stack.push(nei);
                        seen[nei] = true;
                    }
                }
            }
        }

        return ans;
    }
}