LintCode - Number of Islands
Given a boolean 2D matrix,0is represented as the sea,1is represented as the island. If two 1 is adjacent, we consider them in the same island. We only consider up/down/left/right adjacent.
Find the number of islands.
Example
Given graph:
[
[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[0, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 1]
]
return 3.
Analysis: Example
Given graph:
[
[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[0, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 1]
]
Solution 1.Use recursion to mark all neighboring coordindates around each 1 encounter to be 0.
public int numIslands(boolean[][] grid){
int numOfIslands = 0;
if (grid == null || grid.length == 0 || grid[0].length == 0){
return numOfIslands;
}
int[][] marked = new int[grid.length][grid[0].length];
for (int i = 0; i < grid.length; i++){
for (int j = 0; j < grid[i].length; j++){
if (grid[i][j] == true){
helper(i, j, grid);
numOfIslands++;
}
}
}
return numOfIslands;
}
public void helper(int row, int column, boolean[][] grid){
int rowLowerBound = row - 1 > 0 ? row - 1: 0;
int columnLowerBound = column - 1 > 0 ? column - 1 : 0;
int rowUpperBound = row + 1 < grid.length - 1 ? row + 1 : grid.length - 1;
int columnUpperBound = column + 1 < grid[0].length - 1 ? column + 1 : grid[0].length - 1;
grid[row][column] = false;
for (int i = rowLowerBound; i <= rowUpperBound; i++){
if (grid[i][column] == true){
helper(i, column, grid);
}
}
for (int j = columnLowerBound; j <= columnUpperBound; j++){
if (grid[row][j] == true){
helper(row, j, grid);
}
}
}
}
Solution 2. Use iteration instead of recursion.
private class Coordinates{
int x, y;
public Coordinates(int x, int y){
this.x = x;
this.y = y;
}
}
public int numIslands(boolean[][] grid){
int numOfIslands = 0;
if (grid == null || grid.length == 0 || grid[0].length == 0){
return numOfIslands;
}
for (int i = 0; i < grid.length; i++){
for (int j = 0; j < grid[i].length; j++){
if (grid[i][j] == true){
helper(i, j, grid);
numOfIslands++;
}
}
}
return numOfIslands;
}
public void helper(int row, int column, boolean[][] grid){
Queue<Coordinates> queue = new LinkedList<Coordinates>();
queue.offer(new Coordinates(row, column));
while (!queue.isEmpty()){
Coordinates coordinate = queue.poll();
grid[coordinate.x][coordinate.y] = false;
int rowLowerBound = coordinate.x - 1 > 0 ? coordinate.x - 1: 0;
int columnLowerBound = coordinate.y - 1 > 0 ? coordinate.y - 1 : 0;
int rowUpperBound = coordinate.x + 1 < grid.length - 1 ? coordinate.x + 1 : grid.length - 1;
int columnUpperBound = coordinate.y + 1 < grid[0].length - 1 ? coordinate.y + 1 : grid[0].length - 1;
for (int i = rowLowerBound; i <= rowUpperBound; i++){
if (grid[i][coordinate.y] == true){
queue.offer(new Coordinates(i, coordinate.y));
}
}
for (int j = columnLowerBound; j <= columnUpperBound; j++){
if (grid[coordinate.x][j] == true){
queue.offer(new Coordinates(coordinate.x, j));
}
}
}
}
Number Of Islands2
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
Givenn=3,m=3, array of pair A =[(0,0),(0,1),(2,2),(2,1)].
return[1,1,2,2].
Analysis
Use the BFS search on checking the number of the neighboring islands after each operation because each operation would eliminate these neighboring islands. However, it sucks at performance. Whenever it comes to questions about unions, use the Union-Find data structure will greatly improve the performance. Two places to pay attentions:
- how two dimention coordinates is convert to one dimention
- for each neighboring island check, the parent of the point in question is recalculated to reflect the latest parent-child relationship updated in the previous loop.
Solution
int[] deltaX = new int[]{1, -1, 0, 0};
int[] deltaY = new int[]{0, 0, 1, -1};
int[] father = null;
public int findParent(int a){
while (father[a] == a){
return a;
}
return father[a] = findParent(father[a]);
}
public List<Integer> numIslands2(int n, int m, Point[] operators) {
List<Integer> result = new ArrayList<Integer>();
if (operators == null || operators.length == 0 || n == 0 || m == 0){
return result;
}
father = new int[n * m];
for (int i = 0; i < n * m; i++){
father[i] = i;
}
int[][] matrix = new int[n][m];
int count = 0;
for (Point point : operators){
if (inBound(matrix, point)){
if (matrix[point.x][point.y] != 1){
matrix[point.x][point.y] = 1;
int neighboursIsland = countNeighborSeperateIsland(matrix, point);
count = count - neighboursIsland + 1;
}
}
result.add(count);
}
return result;
}
public int convert2Id(int x, int y, int len){
return x * len + y;
}
public void union(int a, int b){
int aParent = findParent(a);
int bParent = findParent(b);
if (aParent != bParent){
father[aParent] = bParent;
}
}
public int countNeighborSeperateIsland(int[][] matrix, Point point){
int count = 0;
for (int i = 0; i < deltaX.length; i++){
Point newPoint = new Point(point.x + deltaX[i], point.y + deltaY[i]);
if (inBound(matrix, newPoint) && matrix[newPoint.x][newPoint.y] == 1){
int aParent = findParent(convert2Id(point.x, point.y, matrix[0].length));
int bParent = findParent(convert2Id(newPoint.x, newPoint.y, matrix[0].length));
if (aParent != bParent){
count++;
union(aParent, bParent);
}
}
}
return count;
}
public boolean inBound(int[][] matrix, Point point){
if (point.x < 0 || point.y < 0 || point.x >= matrix.length || point.y >= matrix[0].length){
return false;
}
return true;
}