Massive Algorithms: November 2018

LeetCode 947 - Most Stones Removed with Same Row or Column

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

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 <= stones.length <= 1000
0 <= stones[i][j] < 10000

Approach 2: Union-Find
https://www.jianshu.com/p/30d2058db7f7

如果两个石头在同行或者同列，两个石头就是连接的。连在一起的石头，可以组成一个连通图。每一个连通图至少会剩下1个石头。
所以我们希望存在一种思路，每个连通图都只剩下1个石头。
这样这题就转化成了数岛屿的问题。

5. 构造移走石头方案

逆向思维，来看一下，如果开始只有一个石头，每次都只能放一个新石头在同行或同列，我们能否构造出整个岛屿。
还是不难得，可以用dfs里查找石头的顺序放，就可以构造整个岛屿了。
反之，按照反序也可以移走整个岛屿直到剩下一个石头。

https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/discuss/199168/standard-union-find-solution

Time Complexity: $O(N \log N)$ , where $N$ is the length of stones. (If we used union-by-rank, this can be $O(N * \alpha(N))$ , where $\alpha$ is the Inverse-Ackermann function.)
Space Complexity: $O(N)$

    class UnionFind {
        int[] parent;
        int[] rank;
        int count;

        public UnionFind(int n) { // for problem 200
            parent = new int[n];
            rank = new int[n];
            count = n;
            for (int i = 0; i < n; ++i) {
                parent[i] = i;
                rank[i] = 0;
            }
        }

        public int find(int x) { // path compression
            // only the rank of the root matters, used in union op.
            if (parent[x] != x)
                parent[x] = find(parent[x]);
            return parent[x];
        }

        public void union(int x, int y) { // union with rank
            int rootx = find(x);
            int rooty = find(y);
            if (rootx != rooty) {
                if (rank[rootx] > rank[rooty]) {
                    parent[rooty] = rootx;
                } else {
                    parent[rootx] = rooty;
                    if (rootx == rooty)
                        rank[rooty] += 1;
                }
                count--;
            }
        }

        public int getCount() {
            return count;
        }
    }

    public int removeStones(int[][] stones) {
        // if any two points are on the same column or row, they are connected as a
        // edge.
        // find connected component, and remove all but one.
        // count the number of disjoint components.
        int n = stones.length;
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isConnected(stones[i], stones[j]))
                    uf.union(i, j);
            }
        }
        return n - uf.getCount();

    }

    private boolean isConnected(int[] p1, int[] p2){
        return p1[0] == p2[0] || p1[1] == p2[1];
    }

http://shibaili.blogspot.com/2018/11/947-most-stones-removed-with-same-row.html

X. O(N)
https://blog.csdn.net/fuxuemingzhu/article/details/84500642
我们不用对石头进行两两判断，而是对他们的横纵坐标同等看待。怎么区分横纵坐标呢？使用的方法是把纵坐标+10000，这样行的索引没变，纵坐标的范围跑到了后面去了。

这个做法的思路是，一个坐标其实就是把横纵坐标对应的两个区域进行了链接。所以，只需要对stones进行一次遍历把对应的区域链接到一起即可。在完成链接之后，我们最后统计一下有多少个独立的区域，需要使用set+find

int removeStones(vector<vector<int>>& stones) {
if(stones.size() <= 1) return 0;
int N = stones.size();
vector<int> p(20000, -1);
for(auto stone : stones){
u(p, stone[0], stone[1] + 10000);
}
set<int> parents;
for(auto stone : stones){
parents.insert(f(p, stone[0]));
}
return N - parents.size();
}
private:
int f(vector<int> &p, int x){
if(p[x] == -1) return x;
return f(p, p[x]);
}

void u(vector<int> &p, int x, int y){
int px = f(p, x);
int py = f(p, y);
if(px != py){
p[px] = py;
}
}

https://www.jianshu.com/p/30d2058db7f7

我们之前的思路是，对石头所在point进行搜索。
有了以上代码，我们就会发现，其实我们搜索的元素是行列的index。
我们以为是行列把石头连接在了一起。
换个角度思考，也可以是一个石头把它所在行列坐标连在了一起。
我们的输入是所有的石头，每个石头都固定连接两个元素。
想到这里，union find的思路就已经呼之欲出了。

https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/discuss/197668/Count-the-Number-of-Islands-O(N)

One sentence to solve:
Connected stones can be reduced to 1 stone,
the maximum stones can be removed = stones number - islands number.
so just count the number of "islands".

1. Connected stones

Two stones are connected if they are in the same row or same col.
Connected stones will build a connected graph.
It's obvious that in one connected graph,
we can't remove all stones.

We have to have one stone left.
An intuition is that, in the best strategy, we can remove until 1 stone.

I guess you may reach this step when solving the problem.
But the important question is, how?

2. A failed strategy

Try to remove the least degree stone
Like a tree, we try to remove leaves first.
Some new leaf generated.
We continue this process until the root node left.

However, there can be no leaf.
When you try to remove the least in-degree stone,
it won't work on this "8" like graph:
[[1, 1, 0, 0, 0],
[1, 1, 0, 0, 0],
[0, 1, 1, 0, 0],
[0, 0, 1, 1, 1],
[0, 0, 0, 1, 1]]

The stone in the center has least degree = 2.
But if you remove this stone first,
the whole connected stones split into 2 parts,
and you will finish with 2 stones left.

3. A good strategy

In fact, the proof is really straightforward.
You probably apply a DFS, from one stone to next connected stone.
You can remove stones in reversed order.
In this way, all stones can be removed but the stone that you start your DFS.

One more step of explanation:
In the view of DFS, a graph is explored in the structure of a tree.
As we discussed previously,
a tree can be removed in topological order,
from leaves to root.

4. Count the number of islands

We call a connected graph as an island.
One island must have at least one stone left.
The maximum stones can be removed = stones number - islands number

The whole problem is transferred to:
What is the number of islands?

You can show all your skills on a DFS implementation,
and solve this problem as a normal one.

5. Unify index

Struggle between rows and cols?
You may duplicate your codes when you try to the same thing on rows and cols.
In fact, no logical difference between col index and rows index.

An easy trick is that, add 10000 to col index.
So we use 0 ~ 9999 for row index and 10000 ~ 19999 for col.

6. Search on the index, not the points

When we search on points,
we alternately change our view on a row and on a col.

We think:
a row index, connect two stones on this row
a col index, connect two stones on this col.

In another view：
A stone, connect a row index and col.

Have this idea in mind, the solution can be much simpler.
The number of islands of points,
is the same as the number of islands of indexes.

7. Union-Find

I use union find to solve this problem.
As I mentioned, the elements are not the points, but the indexes.

for each point, union two indexes.
return points number - union number

Copy a template of union-find,
write 2 lines above,
you can solve this problem in several minutes.

    Map<Integer, Integer> f = new HashMap<>();
    int islands = 0;

    public int removeStones(int[][] stones) {
        for (int i = 0; i < stones.length; ++i)
            union(stones[i][0], ~stones[i][1]);
        return stones.length - islands;
    }

    public int find(int x) {
        if (f.putIfAbsent(x, x) == null)
            islands++;
        if (x != f.get(x))
            f.put(x, find(f.get(x)));
        return f.get(x);
    }

    public void union(int x, int y) {
        x = find(x);
        y = find(y);
        if (f.get(x) != y) {
            f.put(find(x), find(y));
            islands--;
        }
    }

https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/discuss/197693/Java-Union-Find

If stone a and stone b are in the same column/row, we connect them as a component
One component can be removed to one stone left at least.
The largest possible number of moves we can make = Total stones count - count of stones left = Total stones count - count of components.

    int count = 0;
    public int removeStones(int[][] stones) {
        Map<String, String> parent = new HashMap<>();
        count = stones.length;
        // init Union Find
        for (int[] stone : stones) {
            String s = stone[0] + " " + stone[1];
            parent.put(s, s);
        }
        for (int[] s1 : stones) {
            String ss1 = s1[0] + " " + s1[1];
            for (int[] s2 : stones) {
                if (s1[0] == s2[0] || s1[1] == s2[1]) { // in the same column or row
                    String ss2 = s2[0] + " " + s2[1];
                    union(parent, ss1, ss2);
                }
            }
        }
        return stones.length - count;
    }
    private void union(Map<String, String> parent, String s1, String s2) {
        String r1 = find(parent, s1), r2 = find(parent, s2);
        if (r1.equals(r2)) {
            return;
        }
        parent.put(r1, r2);
        count--;
    }
    private String find(Map<String, String> parent, String s) {
        if (!parent.get(s).equals(s)) {
            parent.put(s, find(parent, parent.get(s)));
        }
        return parent.get(s);
    }

As in Approach 1, we will need to consider components of an underlying graph. A "Disjoint Set Union" (DSU) data structure is ideal for this.

Let's connect row i to column j, which will be represented by j+10000. The answer is the number of components after making all the connections.

Note that for brevity, our DSU implementation does not use union-by-rank. This makes the asymptotic time complexity larger.





Time Complexity:  $O(N \log N)$ , where  $N$  is the length of stones. (If we used union-by-rank, this can be  $O(N * \alpha(N))$ , where  $\alpha$  is the Inverse-Ackermann function.)


Space Complexity:  $O(N)$ .

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);

  }

X. DFS
Connect row and col
https://github.com/sherrysack/leetcode-memo/blob/master/947MostStonesRemovedWithSameRoworColumn.md

    public int removeStones(int[][] stones) {
        //dfs find all the connected stones
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
        for(int[] stone: stones) {
            if(!map.containsKey(stone[0])) {
                map.put(stone[0], new ArrayList<Integer>());
            }
            map.get(stone[0]).add(stone[1]+10000);
            if(!map.containsKey(stone[1]+10000)) {
                map.put(stone[1]+10000, new ArrayList<Integer>());
            }
            map.get(stone[1]+10000).add(stone[0]);
        }
        Set<Integer> visited = new HashSet<>();
        int island = 0;
        for(int[] stone: stones) {
            if(!visited.contains(stone[0])) {
                island++;
                dfs(visited, stone[0], map);
                dfs(visited, stone[1]+10000, map);
            }
        }
        return stones.length-island;
    }
    private void dfs(Set<Integer> visited, int a, Map<Integer, ArrayList<Integer>> map) {
        visited.add(a);
        List<Integer> lists = map.get(a);
        for(Integer tar: lists) {
            if(!visited.contains(tar)) {
                dfs(visited, tar, map);
            }
        } 
    }

Approach 1: Depth-First Search
https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/discuss/201308/Simple-DFS-O(N2)-solutio

Iterate over all elements and visit each if not visited already.
During each visit, iterate over all elements and visit each if not visited already and either the column or row is the same as the element we are currently visiting.

    int dfs(int i, boolean[] visited, int[][] stones) {
        visited[i] = true;
        int size = 1;
        for(int j = 0; j < stones.length; j++) {
            if(!visited[j] && (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1])) {
                size += dfs(j, visited, stones);
            }
        }
        return size;
    }
    public int removeStones(int[][] stones) {
        int result = 0;
        boolean[] visited = new boolean[stones.length];
        for(int i = 0; i < stones.length; i++) {
            if(!visited[i])
            result += dfs(i, visited, stones) - 1;
        }
        return result;
    }

https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/discuss/197874/Java-DFS-solution-!!!

    public int removeStones(int[][] stones) {
        Map<Integer, Set<Integer>> rSet = new HashMap<>(), cSet = new HashMap<>();
        for(int[] e : stones) {
            int r = e[0], c = e[1];
            rSet.putIfAbsent(r, new HashSet<>());
            cSet.putIfAbsent(c, new HashSet<>());
            rSet.get(r).add(c);
            cSet.get(c).add(r);
        }
        
        int count = 0;
        Set<String> v = new HashSet<>();
        for(int[] e : stones) {
            String key = e[0]+","+e[1];
            if(!v.contains(key)) {
                count++;
                v.add(key);
                dfs(e[0], e[1], rSet, cSet, v);
            }
        }
        return stones.length - count;
    }
    
    void dfs(int r, int c, Map<Integer, Set<Integer>> rSet, Map<Integer, Set<Integer>> cSet, Set<String> v) {
        for(int y : rSet.get(r)) {
            String key = r+","+y;
            if(!v.contains(key)) {
                v.add(key);
                dfs(r, y, rSet, cSet, v);
            }
        }
        
        for(int x : cSet.get(c)) {
            String key = x+","+c;
            if(!v.contains(key)) {
                v.add(key);
                dfs(x, c, rSet, cSet, v);
            }
        }        
    }

Let's say two stones are connected by an edge if they share a row or column, and define a connected component in the usual way for graphs: a subset of stones so that there doesn't exist an edge from a stone in the subset to a stone not in the subset. For convenience, we refer to a component as meaning a connected component.

The main insight is that we can always make moves that reduce the number of stones in each component to 1.

Firstly, every stone belongs to exactly one component, and moves in one component do not affect another component.

Now, consider a spanning tree of our component. We can make moves repeatedly from the leaves of this tree until there is one stone left.

Algorithm

To count connected components of the above graph, we will use depth-first search.

For every stone not yet visited, we will visit it and any stone in the same connected component. Our depth-first search traverses each node in the component.

For each component, the answer changes by -1 + component.size.

Time Complexity: $O(N^2)$ , where $N$ is the length of stones.
Space Complexity: $O(N^2)$ .

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;

}

https://zhanghuimeng.github.io/post/leetcode-947-most-stones-removed-with-same-row-or-column/

一种方法是，构造一颗这个子树的生成树。（从一个无向连通图能够生成一颗生成树这件事应该够显然的了）然后不断移除这棵树的叶子结点，直到最后只剩下根结点。[1]

当然，事实上不需要真的把这些都构造出来，只要知道就可以了。