Lintcode 1641. Max Remove Order

Give a m * n board with a value of 0 or 1. At each step we can turn a 1 into 0 if there is another 1 in the same row or column. Return the max number of 1 we can turn into 0.

Example

Example 1:

Input：[[1,1,1,1],[1,1,0,1],[1,0,1,0]]
Output：8
Explanation:
In the board
1, 1, 1, 1
1, 1, 0, 1
1, 0, 1, 0
We can remove 1 from right to left, from bottom to top, until there is only one 1 at (0, 0). Totally 8 removed.

Example 2:

Input：[[1,0],[1,0]]
Output：1
Explanation:
In the board
1, 0
1, 0
We can only remove (0,0) or (1,0)

Notice

n and m do not exceed $50$

Solution:

Use Union Find.

Consider from a simpler example. [1, 1, 1, 1]. We can remove three 1s from the set until the last one. So if we scan from left to right, up to bottom, for each element if the value is 1, we connect to the right-most element from the row and bottom-most element from the column. At the end, how many elements we cannot remove? It's the number of connected components. 

Code (Java):

public class Solution {
    /**
     * @param mp: the board
     * @return: the max number of points we can remove
     */
    public int getAns(int[][] mp) {
        // Write your code here.
        if (mp == null || mp.length == 0) {
            return 0;
        }
        
        int m = mp.length;
        int n = mp[0].length;
        
        int numOnes = 0;
        
        // cols[i]: for ith col, the index of the bottom-most one
        // rows[i], for ith row, the index of the right-most one
        int[] rows = new int[m];
        int[] cols = new int[n];
        
        UF uf = new UF(mp);
        
        // step 1: calculate the number of 1s and the right-most position and 
        // bottom-most position of the 1s
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mp[i][j] == 1) {
                    numOnes++;
                    rows[i] = j;
                    cols[j] = i;
                }
            }
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mp[i][j] == 1) {
                    uf.connect(i * n + j, i * n + rows[i]);
                    uf.connect(i * n + j, cols[j] * n + j);
                }
            }
        }
        
        return numOnes - uf.getNumCC();
        
    }
}

class UF {
    private int[] parents;
    private int numCC;
    
    public UF (int[][] mp) {
        int m = mp.length;
        int n = mp[0].length;
        
        parents = new int[m * n];
    
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mp[i][j] == 1) {
                    parents[i * n + j] = i * n + j;
                    numCC++;
                }
            }
        }
    }
    
    public int find(int a) {
        int root = a;
        
        while (parents[root] != root) {
            root = parents[root];
        }
        
        while (root != a) {
            int parent = parents[a];
            parents[a] = root;
            a = parent;
        }
        
        return root;
    }
    
    public void connect(int a, int b) {
        int pa = find(a);
        int pb = find(b);
        
        if (parents[pa] != pb) {
            parents[pa] = pb;
            numCC--;
        }
    }
    
    public int getNumCC() {
        return numCC;
    }
}