QuickUnion method


  • 0
    K

    Well, this took me a while to write because all the possible scenarios when you connecting the O's. Basically, I get the QuickUnionWithPathCompression (path compression is not required here, I just type it to practice a bit). The idea is simple, loop from row= 1 to 2nd last and col = 1 to 2nd last. For each cell, we search four different directions. If current cell is 'O' and its neighbor is 'O' we union them. Because the nature of implementation of this data structure, we have to make sure edge cell are the second parameter of the union, and use of isBoundary(qu.find(flat(x, y))) to union is required.
    The overall performance is bad though :)
    QuickUnion Utility Class

        private class QuickUnion{
            private int count;
            private int[] parent;
            public QuickUnion(int n){
                count = n;
                parent = new int[n];
                for (int i = 0; i < n; i++){
                    parent[i] = i;
                }
            }
            
            public int count(){
                return count;
            }
            
            public int find(int p){
                int root = p;
                while (root != parent[root])
                    root = parent[root];
                while (p != root){
                    int newP = parent[p];
                    parent[p] = root;
                    p = newP;
                }
                return root;
            }
            
            public void union(int p, int q){
                int rootP = find(p);
                int rootQ = find(q);
                if (rootP == rootQ) return;
                parent[rootP] = rootQ;
            }
            
            public boolean connected(int p, int q){
                return find(p) == find(q);
            }
        }
    

    Solution

    	private int m, n;
    
    	private int flat(int i, int j) {
    		return i * n + j;
    	}
    
    	private boolean isBoundary(int p) {
    		int x = p / n, y = p % n;
    		return isBoundary(x, y);
    	}
    
    	private boolean isBoundary(int x, int y) {
    		return x == 0 || x == m - 1 || y == 0 || y == n - 1;
    	}
    
    	public void solve(char[][] board) {
    		if (board == null || board.length < 3 || board[0].length < 3) return;
    		m = board.length;
    		n = board[0].length;
    		QuickUnion qu = new QuickUnion(m * n);
    		int[][] directions = { { 0, -1 }, { -1, 0 }, { 0, 1 }, { 1, 0 } };
    		for (int row = 1; row < m - 1; row++) {
    			for (int col = 1; col < n - 1; col++) {
    				if (board[row][col] == 'O') {
    					for (int[] direction : directions) {
    						int x = row + direction[0], y = col + direction[1];
    						int current = flat(row, col);
    						int neighbor = flat(x, y);
    						if (board[x][y] == 'O' && !qu.connected(current, neighbor)) {
    							if (isBoundary(qu.find(neighbor))) {
    								qu.union(current, neighbor);
    							} else {
    								qu.union(neighbor, current);
    							}
    						}
    					}
    				}
    			}
    		}
    		for (int row = 1; row < m - 1; row++) {
    			for (int col = 1; col < n - 1; col++) {
    				int p = qu.find(flat(row, col));
    				if (!isBoundary(p)) board[row][col] = 'X';
    			}
    		}
    	}
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.