LeetCode - Algorithms - 200. Number of Islands

Whenever possible, steal code.
Keep it simple, stupid.
– Programming Pearls, Jon Bentley.

Problem

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.

Java

BFS

1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int numIslands(char[][] grid) {
        int h = grid.length;
        if (h == 0)
            return 0;
        int w = grid[0].length;
        int r = 0;

        boolean[][] visited = new boolean[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                visited[i][j] = false;
            }
        }

        Queue<Integer[]> queue = new LinkedList<>();
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (!visited[i][j] && grid[i][j] == '1') {
                    queue.add(new Integer[]{i,j});
                    BFS(queue, grid, visited);
                    r++;
                }
            }
        }

    	return r;
    }

    public void BFS(Queue<Integer[]> queue, char[][] islandGrid, boolean[][] visited) {

        int H = islandGrid.length;
        int L = islandGrid[0].length;

        while (queue.isEmpty() == false) {

            Integer[] x = queue.remove();
            int row = x[0];
            int col = x[1];

            if(row<0 || col<0 || row>=H || col>=L || visited[row][col] || islandGrid[row][col]!='1')
                continue;

            visited[row][col]=true;
            queue.add(new Integer[]{row, (col-1)});
            queue.add(new Integer[]{row, (col+1)});
            queue.add(new Integer[]{(row-1), col});
            queue.add(new Integer[]{(row+1), col});
        }
    }
}

Submission Detail

  • 47 / 47 test cases passed.
  • Runtime: 10 ms, faster than 5.88% of Java online submissions for Number of Islands.
  • Memory Usage: 41.6 MB, less than 55.82% of Java online submissions for Number of Islands.

2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class Solution {
    final static int d[][] = {
			{0,1},
			{1,0},
			{0,-1},
			{-1,0}
	};
    
    public int numIslands(char[][] grid) {       
        int h = grid.length;
        if (h == 0)
            return 0;
        int w = grid[0].length;
        
        int r = 0;

        boolean[][] visited = new boolean[h][w];

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                visited[i][j] = false;
            }
        }

        Queue<Point> queue = new LinkedList<>();

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (!visited[i][j] && grid[i][j] == '1') {
                    queue.add(new Point(i,j));
                    bfs(queue, grid, visited);
                    r++;
                }
            }
        }
        
    	return r;        
    }
    
    public void bfs(Queue<Point> queue, char[][] islandGrid, boolean[][] visited) {

        int h = islandGrid.length;
        int w = islandGrid[0].length;

        while (queue.isEmpty() == false) {
        	Point curr = queue.poll();
            int row = curr.x;
            int col =  curr.y;
            if (isValid(islandGrid, visited, h, w, row, col)) {
                visited[row][col]=true;
				for (int i = 0; i < 4; i++) {
					int x = curr.x + d[i][0];
					int y = curr.y + d[i][1];
					queue.add(new Point(x, y));
				}
            }
        }
    }
    
	private boolean isValid(char[][] grid, boolean[][] visited, int width, int height, int row, int col) {
		return (row >= 0) && (row < width) && (col >= 0) && (col < height) && grid[row][col] == '1' && !visited[row][col];
	}
    
    class Point {
		int x;
		int y;

		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

Submission Detail

  • 47 / 47 test cases passed.
  • Runtime: 5 ms, faster than 15.24% of Java online submissions for Number of Islands.
  • Memory Usage: 42.3 MB, less than 17.21% of Java online submissions for Number of Islands.

union–find

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
class Solution {
    final static int d[][] = {
			{0,1},
			{1,0},
			{0,-1},
			{-1,0}
	};
    
    public int numIslands(char[][] grid) {       
		int h = grid.length;
		if (h == 0)
			return 0;
		int w = grid[0].length;

		int N = 0;
		List<Point> ptlist = new ArrayList<Point>();
		Map<String, Integer> map = new HashMap<String, Integer>();
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (grid[i][j] == '1') {
					Point pt = new Point(i,j);
					ptlist.add(pt);
					map.put(i+","+j, N++);
				}
			}
		}

		UF uf = new UF(N);
		for (int i = 0; i < N; i++) {
			Point curr = ptlist.get(i);
			int row = curr.x;
			int col = curr.y;
			for (int k = 0; k < 4; k++) {
				int x = row + d[k][0];
				int y = col + d[k][1];
				if (isValid(grid, h, w, x, y)) {
					uf.union(i, map.get(x + "," + y));
				}
			}
		}

		return uf.count();        
    }
    
    
	private boolean isValid(char[][] grid, int width, int height, int row, int col) {
		return (row >= 0) && (row < width) && (col >= 0) && (col < height) && grid[row][col] == '1';
	}
    
    class Point {
		int x;
		int y;

		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

class UF {
    private int[] parent;
    private byte[] rank;
    private int count;

    public UF(int n) {
        if (n < 0) throw new IllegalArgumentException();
        count = n;
        parent = new int[n];
        rank = new byte[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    public int find(int p) {
        validate(p);
        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }

    public int count() {
        return count;
    }

    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) return;

        if      (rank[rootP] < rank[rootQ]) parent[rootP] = rootQ;
        else if (rank[rootP] > rank[rootQ]) parent[rootQ] = rootP;
        else {
            parent[rootQ] = rootP;
            rank[rootP]++;
        }
        count--;
    }

    private void validate(int p) {
        int n = parent.length;
        if (p < 0 || p >= n) {
            throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n-1));
        }
    }
}

Submission Detail

  • 47 / 47 test cases passed.
  • Runtime: 28 ms, faster than 5.05% of Java online submissions for Number of Islands.
  • Memory Usage: 45.3 MB, less than 5.12% of Java online submissions for Number of Islands.

ref