Number of Islands
#DFS #UnionFind
Question
Given a boolean 2D matrix, find the number of islands.
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.
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.
Tags
Facebook Zenefits Google
Related Problems
Medium Surrounded Regions Hard Number of Islands II
Analysis
思路一：
此题可以考虑用Union Find，不过更简单的是用BFS或者DFS。
其中DFS结合mark的方法最巧妙简单，n^2循环，扫描grid[i][j], 如果是island的，即grid[i][j] == true，则计数加一（ans++），并对四个方向进行DFS查找，并将所有属于那坐岛屿的点mark为非岛屿。这样扫描过的地方全部会变成非岛屿，而岛屿的数量已被记录。
思路二： Union Find 利用Union Find的find和union操作，对岛屿进行合并计数。因为UnionFind结构一般来说是一维的
| 1 | 2 | 3 | 4 |
-----------------
| 2 | 2 | 2 | 4 |表达了如下的连通结构
1 - 2 4
| /
3因此可以转换二维矩阵坐标为一维数字，M N 的矩阵中`(i,j) -> i N + j`。
建立UnionFind的parent[] (或者 parent hashmap)，初始化各个
parent[i * N + j] = i * N + j，如果grid[i][j] == true，则岛屿计数count++之后再对矩阵遍历一次，当遇到岛屿时，则要检查上下左右四个方向的邻近点，如果也是岛屿则合并，并且count--；
Union Find结构可以用Path Compression和Weighted Union进行优化。
Solution
DFS (3ms AC)
public class Solution {
/**
* @param grid a boolean 2D matrix
* @return an integer
*/
public int numIslands(boolean[][] grid) {
m = grid.length;
if (m == 0) {
return 0;
}
n = grid[0].length;
if (n == 0) {
return 0;
}
int nums = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == false) {
continue;
}
nums++;
dfs(grid, i, j);
}
}
return nums;
}
private void dfs(boolean[][] grid, int i, int j) {
if (i < 0 || i >= m || j < 0 || j >= n) {
return;
}
if (grid[i][j] == true) {
grid[i][j] = false;
dfs(grid, i - 1, j);
dfs(grid, i + 1, j);
dfs(grid, i, j - 1);
dfs(grid, i, j + 1);
}
}
private int m, n;
}DFS (same, just with directional 2D array)
class Solution {
int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public int numIslands(char[][] grid) {
int m = grid.length;
if (m == 0) {
return 0;
}
int n = grid[0].length;
int result = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
dfs(grid, i, j, m, n);
result++;
}
}
}
return result;
}
public void dfs(char[][] grid, int i, int j, int m, int n) {
if (i < 0 || i > m - 1 || j < 0 || j > n - 1 || grid[i][j] != '1') {
return;
}
grid[i][j] = '0';
for (int[] dir : dirs) {
dfs(grid, i + dir[0], j + dir[1], m, n);
}
}
}BFS - (14ms AC)
class Solution {
int[][] dir = new int[][] { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
class Point {
int row;
int col;
Point (int row, int col) {
this.row = row;
this.col = col;
}
}
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int m = grid.length;
int n = grid[0].length;
int numIslands = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
numIslands++;
grid[i][j] = '0';
// BFS
Queue<Point> q = new LinkedList<>();
q.offer(new Point(i, j));
while (!q.isEmpty()) {
Point p = q.poll();
for (int k = 0; k < 4; k++) {
int ni = p.row + dir[k][0];
int nj = p.col + dir[k][1];
if (ni >= 0 && ni < m &&
nj >= 0 && nj < n &&
grid[ni][nj] == '1') {
grid[ni][nj] = '0';
q.offer(new Point(ni, nj));
}
}
}
}
}
}
return numIslands;
}
}BFS - (17ms AC)
class Solution {
private int m, n;
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
m = grid.length;
n = grid[0].length;
int count = 0;
boolean [][] visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1' && !visited[i][j]) {
count++;
bfs(grid, visited, i, j);
}
}
}
return count;
}
// BFS - marking island as visited
private void bfs(char[][] grid, boolean[][] visited, int x, int y) {
int[] dx = {1, 0 , -1, 0};
int[] dy = {0, 1 , 0, -1};
Queue <Integer> qx = new LinkedList<Integer>();
Queue <Integer> qy = new LinkedList<Integer>();
qx.offer(x);
qy.offer(y);
visited[x][y] = true;
while (!qx.isEmpty() && !qy.isEmpty()) {
int cx = qx.poll();
int cy = qy.poll();
// iterate over up, left, right, down 4 direction
for (int k = 0; k < 4; k++) {
int nx = cx + dx[k];
int ny = cy + dy[k];
// if within boundaries and not visited and is a part of island
if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] && grid[nx][ny] == '1') {
visited[nx][ny] = true;
qx.offer(nx);
qy.offer(ny);
}
}
}
}
}Union Find (Verbose, 19 ms AC)
class UnionFind {
public int[] parent;
public int[] size;
// Initialize UnionFind
public UnionFind() {}
public UnionFind(int n) {
this.parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
this.parent[i] = i;
size[i] = 1;
}
}
// Find Method
public int find(int x) {
return compressedFind(x);
}
// Find Method with Path Compression
public int compressedFind(int x) {
while (x != parent[x]) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
// Union Method with Weight
public void union(int x, int y) {
int parentX = find(x);
int parentY = find(y);
if (parentX == parentY) {
return;
}
if (this.size[parentX] < this.size[parentY]) {
this.size[parentY] += this.size[parentX];
this.parent[parentX] = parentY;
} else {
this.size[parentX] += this.size[parentY];
this.parent[parentY] = parentX;
}
}
}
class IslandUnionFind extends UnionFind {
public int count;
public void initIslands(boolean grid[][]) {
count = 0;
int m = grid.length;
int n = grid[0].length;
this.parent = new int[m * n];
this.size = new int[m * n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == true) {
parent[i * n + j] = i * n + j;
count++;
} else {
parent[i * n + j] = -1;
}
this.size[i * n + j] = 1;
}
}
}
public void updateCount(int k) {
count = count + k;
}
public int getCount() {
return count;
}
}
public class Solution {
public boolean insideGrid(int x, int y, int m, int n) {
return (x >= 0 && y >= 0 && x < m && y < n);
}
/**
* @param grid a boolean 2D matrix
* @return an integer
*/
public int numIslands(boolean[][] grid) {
// Check Input
if(grid==null || grid.length==0 || grid[0].length==0) {
return 0;
}
IslandUnionFind uf = new IslandUnionFind();
uf.initIslands(grid);
int m = grid.length;
int n = grid[0].length;
// Helper Direction Array
int[] dx = new int[] {-1, 1, 0, 0};
int[] dy = new int[] {0, 0, -1, 1};
// Row and Column Traversal
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (insideGrid(i, j, m, n) && grid[i][j]) {
// 4 directions for each point
for (int k = 0; k < 4; k++) {
int nx = i + dx[k];
int ny = j + dy[k];
if (insideGrid(nx, ny, m, n) && grid[nx][ny]) {
int cparent = uf.find(i * n + j);
int nparent = uf.find(nx * n + ny);
if (cparent != nparent) {
uf.union(cparent, nparent);
uf.updateCount(-1);
}
}
}
}
}
}
return uf.getCount();
}
}Another Union Find (8ms AC)
class Solution {
int[][] distance = { { 1, 0 }, {-1, 0 }, { 0, 1 }, { 0, -1 } };
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
UnionFind uf = new UnionFind(grid);
int rows = grid.length;
int cols = grid[0].length;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1') {
for (int[] d: distance) {
int x = i + d[0];
int y = j + d[1];
if (x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] == '1') {
int id1 = i * cols + j;
int id2 = x * cols + y;
uf.union(id1, id2);
}
}
}
}
}
return uf.count;
}
class UnionFind {
int[] father;
int m, n;
int count = 0;
UnionFind(char[][] grid) {
m = grid.length;
n = grid[0].length;
father = new int[m * n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
int id = i * n + j;
father[id] = id;
count++;
}
}
}
}
public void union(int node1, int node2) {
int find1 = find(node1);
int find2 = find(node2);
if (find1 != find2) {
father[find1] = find2;
count--;
}
}
public int find(int node) {
if (father[node] == node) {
return node;
}
father[node] = find(father[node]);
return father[node];
}
}
}Solution
Last updated