XYZ CODE: Number of Islands

Problem

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

Example 2:

Input:

11000

00100

00011

Output: 3

Solution

We need to check each grid, otherwise we might miss an island, the time cost at least should be O(MN).

This problem is a standard undirected graph connected component problem. We can model each grid as a graph node, then each node has four edges connected to the neighboring node, then we iterate the nodes and use either dfs or bfs to count the connected components. With a large number of edges, the space complexity will be big, besides, we need to remember the visited edges with a HashSet.

With the following simplify, we can keep the space complexity under O(MN).

This is a grid not a random graph, so we don't need explicit edge, the four neighbors are always located at grid[r-1][c], grid[r+1][c], grid[r][c-1], grid[r][c+1].
We don't need to remember which node has been visited. We just set the value to 0, that means we don't run dfs or bfs on the grid again.

So our algorithm is: we iterate the grid nodes, whenever we meet a 1, we increase the number of islands, then we do a dfs to erase the discovered island from the map. Finally, after we checked all the MN grid, we find the number of islands.

class Solution {

int[][] grid = new int[][]{

{1,1,0,0,0},

{0,0,1,0,0},

{0,0,0,1,1}

};

int nr = grid.length; //4

int nc = grid[0].length; //5

int count = 0;

public static void main(String[] args) {

Solution sol = new Solution();

System.out.println(sol.count());

}

private int count() {

for(int r = 0; r < nr; r++) {

for(int c = 0; c < nc; c++) {

if(grid[r][c] == 1) {

count++; //3

dfs(r, c);

}

return count;

}

private void dfs(int r, int c) {

if(r < 0 || r >= nr || c < 0 || c >= nc) {

return;

}

if(grid[r][c] == 0) {

return;

} else {

grid[r][c] = 0;

dfs(r - 1, c);

dfs(r + 1, c);

dfs(r, c - 1);

dfs(r, c + 1);

}

Alternatively, we can iterate the grid, instead use dfs or bfs to erase islands, we use an union find data structure to keep track of how many islands we found, the union operation (with path compression) takes extra time cost O(1) and union find array takes extra space cost O(NxM). This approach doesn't modify the original grid values.

public class CountIslands {
private static class UnionFind {
private int[] connect;
private int[] sz;
private int count;
public UnionFind(int N) {
count = N;
connect = new int[N];
sz = new int[N];
for(int i = 0; i < N; i++) {
connect[i] = i;
sz[i] = 0;
}
}
public int getCount() {
return count;
}
public int find(int p) {
while(connect[p] != p) {
p = connect[p];
}
return p;
}
public void union(int p, int q) {
int root1 = find(p);
int root2 = find(q);
if(root1 == root2) return;
if(sz[root1] > sz[root2]) {
connect[root2] = root1;
sz[root1] += sz[root2];
} else {
connect[root1] = root2;
sz[root2] += sz[root1];
}
count--;
}
public void decreaseCount() {
count--;
}
}
public static int countIsland(int[][] map, UnionFind uf) {
/*
11000
11000
00100
00011
*/
int N = map.length;//4
int M = map[0].length;//5
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if(map[i][j] == 0) uf.decreaseCount();
else {
if(i == 0) {
if(j > 0 && map[0][j-1] == 1) {
uf.union(j-1, j);
}
} else {
if(j == 0 && map[i-1][0] == 1) {
uf.union(i*M, (i-1)*M);
} else if(j > 0) {
if(map[i-1][j] == 1) {
uf.union(i*M + j, (i-1)*M + j);
}
if(map[i][j-1] == 1) {
uf.union(i*M + j, i*M + j - 1);
}
}
}
}
}
}
return uf.getCount();
}
public static void main(String...args) {
int[][] map = new int[][] {
{1,1,0,0,0},
{1,1,0,0,0},
{0,0,1,0,0},
{0,0,0,1,1}
};
UnionFind uf = new UnionFind(map.length * map[0].length);
System.out.println(countIsland(map, uf));
}
}

Time complexity O(MN), space complexity O(MN).