/**
Number of Islands II
A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example:
Given m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]]. Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).
0 0 0
0 0 0
0 0 0
Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.
1 0 0
0 0 0 Number of islands = 1
0 0 0
Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land.
1 1 0
0 0 0 Number of islands = 1
0 0 0
Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.
1 1 0
0 0 1 Number of islands = 2
0 0 0
Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land.
1 1 0
0 0 1 Number of islands = 3
0 1 0
We return the result as an array: [1, 1, 2, 3]
*/
public class NumberOfIslandsII{
/**
Same as the Number of Islands, except that the complexity of DFS and BFS is very high, and it is O(knm). So with the Union-Find approach, the complexity of operating the Kth point is O(K). Let count be 0, do UnionFind every time you add an island, count-- if you find it connected to other islands. Note that with the use of compress find, the time complexity is greatly reduced, because the equalization complexity of compress is O(1).
This problem requires a classic data structure called UnionFind. Take some efforts to learn it at first, like using this Princeton's notes offered by peisi.
This is a basic union-find problem. Given a graph with points being added, we can at least solve:
How many islands in total?
Which island is pointA belonging to?
Are pointA and pointB connected?
The idea is simple. To represent a list of islands, we use trees. i.e., a list of roots. This helps us find the identifier of an island faster. If roots[c] = p means the parent of node c is p, we can climb up the parent chain to find out the identifier of an island, i.e., which island this point belongs to:
Do root[root[roots[c]]]... until root[c] == c;
To transform the two dimension problem into the classic UF, perform a linear mapping:
int id = n * x + y;
Initially assume every cell are in non-island set {-1}. When point A is added, we create a new root, i.e., a new island. Then, check if any of its 4 neighbors belong to the same island. If not, union the neighbor by setting the root to be the same. Remember to skip non-island cells.
UNION operation is only changing the root parent so the running time is O(1).
FIND operation is proportional to the depth of the tree. If N is the number of points added, the average running time is O(logN), and a sequence of 4N operations take O(NlogN). If there is no balancing, the worse case could be O(N^2).
Remember that one island could have different roots[node] value for each node. Because roots[node] is the parent of the node, not the highest root of the island. To find the actually root, we have to climb up the tree by calling findIsland function.
Here I've attached my solution. There can be at least two improvements: union by rank & path compression. However I suggest first finish the basis, then discuss the improvements.
ref:http://massivealgorithms.blogspot.com/2015/11/like-coding-leetcode-305-number-of.html
*/
public List<Integer> numIslands2(int m, int n, int[][] positions) {
List<Integer> result = new ArrayList<Integer>();
int count = 0;
HashMap<Integer, Integer> map = new HashMap<>();
//the possible navigation from a cell-> left,right, up, and down
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
for (int[] pos : positions) {
int x = pos[0];
int y = pos[1];
////2D converted to 1D --> point = n*x+y, save to island
map.put(x * n + y, x * n + y);
//after added the new island, increase count
count++;
for (int[] d : dirs) {
int dirx = x + d[0];
int diry = y + d[1];
//calculate each neighbor --> 2D to 1D, save to neighbor
int npos = dirx * n + diry;
//continue if neighbor position invalid or neighbor ancestor remains (no island)
if (dirx < 0 || diry < 0 || dirx >= m || diry >= n || !map.containsKey(npos)) {
continue;
}
//FIND the neighbor ancestor (the existing island)
int fa_x = find(x * n + y, map);
int fa_y = find(npos, map);
//when neighbor's island is a different island, do UNION, and reduce count
if (fa_x != fa_y) {
map.put(fa_x, fa_y);
count--;
}
}
//operation ended, add count of current operation into result list
result.add(count);
}
return result;
}
private int find(int pos, HashMap<Integer, Integer> map) {
int father = map.get(pos);
while (father != map.get(father)) {
father = map.get(father);
}
// find compress here
int temp = -1;
while (pos != map.get(pos)) {
temp = map.get(pos);
map.put(pos, father);
pos = temp;
}
//end of the compress
return father;
}
}
Number of Islands II
A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example:
Given m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]]. Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).
0 0 0
0 0 0
0 0 0
Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.
1 0 0
0 0 0 Number of islands = 1
0 0 0
Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land.
1 1 0
0 0 0 Number of islands = 1
0 0 0
Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.
1 1 0
0 0 1 Number of islands = 2
0 0 0
Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land.
1 1 0
0 0 1 Number of islands = 3
0 1 0
We return the result as an array: [1, 1, 2, 3]
*/
public class NumberOfIslandsII{
/**
Same as the Number of Islands, except that the complexity of DFS and BFS is very high, and it is O(knm). So with the Union-Find approach, the complexity of operating the Kth point is O(K). Let count be 0, do UnionFind every time you add an island, count-- if you find it connected to other islands. Note that with the use of compress find, the time complexity is greatly reduced, because the equalization complexity of compress is O(1).
This problem requires a classic data structure called UnionFind. Take some efforts to learn it at first, like using this Princeton's notes offered by peisi.
This is a basic union-find problem. Given a graph with points being added, we can at least solve:
How many islands in total?
Which island is pointA belonging to?
Are pointA and pointB connected?
The idea is simple. To represent a list of islands, we use trees. i.e., a list of roots. This helps us find the identifier of an island faster. If roots[c] = p means the parent of node c is p, we can climb up the parent chain to find out the identifier of an island, i.e., which island this point belongs to:
Do root[root[roots[c]]]... until root[c] == c;
To transform the two dimension problem into the classic UF, perform a linear mapping:
int id = n * x + y;
Initially assume every cell are in non-island set {-1}. When point A is added, we create a new root, i.e., a new island. Then, check if any of its 4 neighbors belong to the same island. If not, union the neighbor by setting the root to be the same. Remember to skip non-island cells.
UNION operation is only changing the root parent so the running time is O(1).
FIND operation is proportional to the depth of the tree. If N is the number of points added, the average running time is O(logN), and a sequence of 4N operations take O(NlogN). If there is no balancing, the worse case could be O(N^2).
Remember that one island could have different roots[node] value for each node. Because roots[node] is the parent of the node, not the highest root of the island. To find the actually root, we have to climb up the tree by calling findIsland function.
Here I've attached my solution. There can be at least two improvements: union by rank & path compression. However I suggest first finish the basis, then discuss the improvements.
ref:http://massivealgorithms.blogspot.com/2015/11/like-coding-leetcode-305-number-of.html
*/
public List<Integer> numIslands2(int m, int n, int[][] positions) {
List<Integer> result = new ArrayList<Integer>();
int count = 0;
HashMap<Integer, Integer> map = new HashMap<>();
//the possible navigation from a cell-> left,right, up, and down
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
for (int[] pos : positions) {
int x = pos[0];
int y = pos[1];
////2D converted to 1D --> point = n*x+y, save to island
map.put(x * n + y, x * n + y);
//after added the new island, increase count
count++;
for (int[] d : dirs) {
int dirx = x + d[0];
int diry = y + d[1];
//calculate each neighbor --> 2D to 1D, save to neighbor
int npos = dirx * n + diry;
//continue if neighbor position invalid or neighbor ancestor remains (no island)
if (dirx < 0 || diry < 0 || dirx >= m || diry >= n || !map.containsKey(npos)) {
continue;
}
//FIND the neighbor ancestor (the existing island)
int fa_x = find(x * n + y, map);
int fa_y = find(npos, map);
//when neighbor's island is a different island, do UNION, and reduce count
if (fa_x != fa_y) {
map.put(fa_x, fa_y);
count--;
}
}
//operation ended, add count of current operation into result list
result.add(count);
}
return result;
}
private int find(int pos, HashMap<Integer, Integer> map) {
int father = map.get(pos);
while (father != map.get(father)) {
father = map.get(father);
}
// find compress here
int temp = -1;
while (pos != map.get(pos)) {
temp = map.get(pos);
map.put(pos, father);
pos = temp;
}
//end of the compress
return father;
}
}
No comments:
Post a Comment