Number of Islands II

LintCode Q 434 - Number of Islands II

Given a n,m which means the row and column of the 2D matrix and an array of pair A( size k). Originally, the 2D matrix is all 0 which means there is only sea in the matrix. The list pair has k operator and each operator has two integer A[i].x, A[i].y means that you can change the grid matrix[A[i].x][A[i].y] from sea to island. Return how many island are there in the matrix after each operator.

Example 1:
Input: n = 4, m = 5, A = [[1,1],[0,1],[3,3],[3,4]] ; Output: [1,1,2,2]
Explanation:

1. 00000
   00000
   00000
   00000
2. 00000
   01000
   00000
   00000
3. 01000
   01000
   00000
   00000
4. 01000
   01000
   00000
   00010
5. 01000
   01000
   00000
   00011

Example 2:
Input: n = 3, m = 3, A = [[0,0],[0,1],[2,2],[2,1]]; Output: [1,1,2,2]

Notice: 0 is represented as the sea, 1 is represented as the island. If two 1 is adjacent, we consider them in the same island. We only consider up/down/left/right adjacent.

Solution

Solution 1 : Union Find

We don’t need an addition array to record if we have visited a node, we can set M[i][i] = 2 to indiate that.

Code:

class UnionFindSet {
	int[] parent;
	
	public UnionFindSet (int size) {
		this.parent = new int[size];
		for (int i = 0; i < size; i++)
			this.parent[i] = i;
	}
	
	public int find (int x) {
		if (x != parent[x]) parent[x] = find(parent[x]);
		return parent[x];
	}
	
	public void union (int x, int y) {
		int px = find(x), py = find(y);
		if (px != py) { parent[py] = px; }
	}
}

private static final int[] DIRS = new int[]{1, 0, -1, 0, 1};
public List<Integer> numIslands2(int R, int C, Point[] operators) {
	List<Integer> res = new ArrayList<>();
	if (R == 0 || C == 0 || operators == null || operators.length == 0)
		return res;
	
	int[][] grid = new int[R][C];

	UnionFindSet ufs = new UnionFindSet(R * C);

	int count = 0;
	for (Point operator: operators) {
		int r = operator.x, c = operator.y;
		if (grid[r][c] != 1) {
			count++;
			grid[r][c] = 1;
			for (int i = 0; i < 4; i++) {
				int nr = r + DIRS[i], nc = c + DIRS[i + 1];
				if (nr < 0 || nc < 0 || nr == R || nc == C 
				|| grid[nr][nc] == 0) continue;
				int pa = ufs.find(r * C + c);
				int npa = ufs.find(nr * C + nc);
				if (pa != npa) {
					count--;
					ufs.union(pa, npa);
				}
			}
		}
		res.add(count);
	}

	return res;
}