Comment on page

# 200.Number-of-Islands

## 题目描述

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. 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 1:
Input:
11110
11010
11000
00000
Output: 1

## 代码

### Approach #1 DFS

Complexity Analysis
• Time complexity : O(_M×N) where M is the number of rows and _N is the number of columns.
• Space complexity : worst case O(_M×N) in case that the grid map is filled with lands where DFS goes by M×_N deep.
class Solution {
public int numIsLands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int nr = grid.length;
int nc = grid.length;
int num_islands = 0;
for (int r = 0; r < nr; r++) {
for (int c = 0; c < nc; c++) {
if (grid[r][c] == '1') {
num_islands++;
dfs(grid, r, c);
}
}
}
return num_islands;
}
private void dfs(char[][] grid, int r, int c) {
int nr = grid.length;
int nc = grid.length;
if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
return;
}
grid[r][c] = '0';
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
}

### Approach #2 BFS

mplexity Analysis
• Time complexity : O(_M×N) where M is the number of rows and _N is the number of columns.
• Space complexity : O(_min(M,N)) because in worst case where the grid is filled with lands, the size of queue can grow up to min(M,,_N).
class Solution {
public int numIsland(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int nr = grid.length;
int nc = grid.length;
int num_islands = 0;
for (int r = 0; r < nr; r++) {
for (int c = 0; c < nc; c++) {
if (grid[r][c] == '1') {
num_islands++;
grid[r][c] = '0'; // mark as visited
while (!neighbors.isEmpty()) {
int id = neighbors.remove();
int row = id / nc;
int col = id % nc;
if ( row - 1 >= 0 && grid[row-1][col] == '1') {
neighbors.add((row - 1) * nc + col);
grid[row-1][col] = '0';
}
if (row + 1 < nr && grid[row+1][col] == '1') {
grid[row+1][col] = '0';
}
if (col - 1 >= 0 && grid[row][col-1] == '1') {
neighbors.add(row * nc + col - 1);
grid[row][col - 1] = '0';
}
if (col + 1 < nc && grid[row][col+1] == '1') {
neighbors.add(row * nc + col + 1);
grid[row][col+1] = '0';
}
}
}
}
}
}
}

### Approach #3 Union Find (aka Disjoint Set) Confusion

class Solution {
class UnionFind {
int count; // # of connected components
int[] parent;
int[] rank;
public UnionFind(char[][] grid) { // for problem 200
count = 0;
int m = grid.length;
int n = grid.length;
parent = new int[m * n];
rank = new int[m * n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '1') {
parent[i * n + j] = i * n + j;
++count;
}
rank[i * n + j] = 0;
}
}
}
public int find(int i) { // path compression
if (parent[i] != i) parent[i] = find(parent[i]);
return parent[i];
}
public void union(int x, int y) { // union with rank
int rootx = find(x);
int rooty = find(y);
if (rootx != rooty) {
if (rank[rootx] > rank[rooty]) {
parent[rooty] = rootx;
} else if (rank[rootx] < rank[rooty]) {
parent[rootx] = rooty;
} else {
parent[rooty] = rootx;
rank[rootx] += 1;
}
--count;
}
}
public int getCount() {
return count;
}
}
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int nr = grid.length;
int nc = grid.length;
int num_islands = 0;
UnionFind uf = new UnionFind(grid);
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
grid[r][c] = '0';
if (r - 1 >= 0 && grid[r-1][c] == '1') {
uf.union(r * nc + c, (r-1) * nc + c);
}
if (r + 1 < nr && grid[r+1][c] == '1') {
uf.union(r * nc + c, (r+1) * nc + c);
}
if (c - 1 >= 0 && grid[r][c-1] == '1') {
uf.union(r * nc + c, r * nc + c - 1);
}
if (c + 1 < nc && grid[r][c+1] == '1') {
uf.union(r * nc + c, r * nc + c + 1);
}
}
}
}
return uf.getCount();
}
}