305. Number of Islands II (union-find)
naive
BFS in leetcode 200, each cell call BFS one time
T: O(mn*mn)
S: O(mn)
union find
T: O(mn)
S: O(mn)
class Solution {
private int[][] dirs = {{1,0},{0,1},{-1,0},{0,-1}};
public List<Integer> numIslands2(int m, int n, int[][] positions) {
List<Integer> res = new ArrayList<>();
if (positions == null || positions.length == 0) {
return res;
}
UnionFind uf = new UnionFind();
boolean[][] isLand = new boolean[m][n];
for (int[] position : positions) {
int x = position[0];
int y = position[1];
if (isLand[x][y]) {
res.add(uf.getNumOfSet());
continue;
}
isLand[x][y] = true;
uf.add(toId(x, y, n));
for (int[] dir : dirs) {
int neighborX = x + dir[0];
int neighborY = y + dir[1];
if (!isValid(neighborX, neighborY, m, n, isLand)) {
continue;
}
uf.union(toId(x, y, n), toId(neighborX, neighborY, n));
}
res.add(uf.getNumOfSet());
}
return res;
}
/*
m = 4, n = 9 (4 row, 9 col)
0 1 2 3 4 5 6 7 8
9 10 11 12 => (1,2) => 1*9 + 2 = 11, x*n + y
*/
private int toId(int x, int y, int n) {
return x*n + y;
}
private boolean isValid(int x, int y, int m, int n, boolean[][] isLand) {
return x >= 0 && x < m && y >= 0 && y < n && isLand[x][y];
}
}
class UnionFind {
private Map<Integer, Integer> parent;
private Map<Integer, Integer> sizeOfSet;
private int numOfSet = 0;
UnionFind() {
this.parent = new HashMap<>();
this.sizeOfSet = new HashMap<>();
}
public void add(int x) {
if (parent.containsKey(x)) {
return;
}
parent.put(x, null);
sizeOfSet.put(x, 1);
numOfSet++;
}
public int find(int x) {
int root = x;
while (parent.get(root) != null) {
root = parent.get(root);
}
while (x != root) {
int xParent = parent.get(x);
parent.put(x, root);
x = xParent;
}
return root;
}
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
parent.put(rootX, rootY);
numOfSet--;
sizeOfSet.put(rootY, sizeOfSet.get(rootX)+sizeOfSet.get(rootY));
}
}
public boolean isConnected(int x, int y) {
return find(x) == find(y);
}
public int getNumOfSet() {
return numOfSet;
}
public int getSizeOfSet(int x) {
if (!sizeOfSet.containsKey(x)) {
return 0;
}
return sizeOfSet.get(find(x));
}
}new version
/*
因為一開始就沒有任何資料, 逐筆加入的, 所以要把加入的 land 記錄下來
*/
class Solution {
int dirs[][] = {{0,1},{1,0},{0,-1},{-1,0}};
public List<Integer> numIslands2(int m, int n, int[][] positions) {
List<Integer> res = new ArrayList<>();
if (positions == null && positions.length == 0) {
return res;
}
boolean[][] isLand = new boolean[m][n];
UnionFind uf = new UnionFind();
for (int[] position : positions) {
int x = position[0];
int y = position[1];
//if (!isLand[x][y]) { // if repeat add same land
isLand[x][y] = true;
uf.add(convertToId(x, y, n));
for (int dir[] : dirs) {
int newX = x + dir[0];
int newY = y + dir[1];
if (!isValid(m, n, newX, newY, isLand)) { // still needs check new x, y is also isLand
continue;
}
uf.union(convertToId(x, y, n),
convertToId(newX, newY, n));
}
//}
res.add(uf.getNumOfSet()); // if repeat add same land
}
return res;
}
private boolean isValid(int m, int n, int x, int y, boolean[][] isLand) {
return x >= 0 && x < m && y >=0 && y < n && isLand[x][y];
}
private int convertToId(int x, int y, int n) {
return x*n + y;
}
}
class UnionFind {
private HashMap<Integer, Integer> parent;
private HashMap<Integer, Integer> sizeOfSet;
private int numOfSet = 0;;
UnionFind() {
parent = new HashMap<>();
sizeOfSet = new HashMap<>();
}
public void add(int x) {
if (parent.containsKey(x)) {
return;
}
parent.put(x, null);
sizeOfSet.put(x, 1);
numOfSet++;
}
public int find(int x) {
int root = x;
while (parent.get(root) != null) {
root = parent.get(root);
}
while (root != x) {
int xParent = parent.get(x);
parent.put(x, root);
x = xParent;
}
return root;
}
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
parent.put(rootX, rootY);
numOfSet--;
sizeOfSet.put(rootX, sizeOfSet.get(rootX)+sizeOfSet.get(rootY));
}
}
public boolean isConnected(int x, int y) {
return find(x) == find(y);
}
public int getSizeOfSet(int x) {
return sizeOfSet.get(find(x));
}
public int getNumOfSet() {
return numOfSet;
}
}final version - simpler union find
T: O(mn)
S: O(mn)
class Solution {
class UnionFind {
int count;
int[] parent;
UnionFind(int n) {
count = 0;
parent = new int[n];
Arrays.fill(parent, -1);
}
public boolean isValid(int i) {
return parent[i] >= 0;
}
public void setParent(int i) {
if (parent[i] == i) {
return;
}
parent[i] = i;
count++;
}
public void union(int i, int j) {
int x = find(i);
int y = find(j);
if (x != y) {
parent[x] = y;
count--;
}
}
public int find(int i) {
if (parent[i] != i) {
parent[i] = find(parent[i]);
}
return parent[i];
}
public int getCount() {
return this.count;
}
}
private static final int[][] DIRS = {{0,1}, {1,0}, {0,-1}, {-1,0}};
public List<Integer> numIslands2(int m, int n, int[][] positions) {
List<Integer> res = new ArrayList<>();
UnionFind uf = new UnionFind(m*n); // notice this, give a whole space
for (int[] position : positions) {
int x = position[0];
int y = position[1];
// and use id to transform x, y
int id = convertToId(x, y, n);
uf.setParent(id);
for (int[] dir : DIRS) {
int newX = x + dir[0];
int newY = y + dir[1];
int newId = convertToId(newX, newY, n);
if (!isValidRange(newX, newY, m, n) || !uf.isValid(newId)) {
continue;
}
// union with id
uf.union(id, newId);
}
res.add(uf.getCount());
}
return res;
}
private int convertToId(int x, int y, int n) {
return x*n + y; // row*col_size + col
}
private boolean isValidRange(int x, int y, int m, int n) {
return x >= 0 && x < m && y >= 0 && y < n;
}
}
/*
[[0,0],[0,1],[1,2],[1,2]]
1 1
1
*/Last updated