[LeetCode] 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:
11110 11010 11000 00000
Answer: 1
Example 2:
11000 11000 00100 00011
Answer: 3
Thought process:
BFS.
- islands = 0.
- Iterate through every number on the grid. For each number, if it's 1:
- islands++.
- Change the number to 0.
- For each neighbor of the number, if it's 1, offer it to the queue.
- Return islands.
Solution 1 (BFS):
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 | class Solution { private final int[][] directions = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } }; public int numIslands(char[][] grid) { int num = 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == '1') { bfs(grid, i, j); num++; } } } return num; } private void bfs(char[][] grid, int row, int col) { grid[row][col] = 'i'; Queue<int[]> queue = new LinkedList<>(); queue.offer(new int[]{ row, col }); while (!queue.isEmpty()) { int[] cell = queue.poll(); for (int i = 0; i < 4; i++) { int nextRow = cell[0] + directions[i][0]; int nextCol = cell[1] + directions[i][1]; if (nextRow >= 0 && nextRow < grid.length && nextCol >= 0 && nextCol < grid[0].length) { if (grid[nextRow][nextCol] == '1') { grid[nextRow][nextCol] = 'i'; queue.offer(new int[]{ nextRow, nextCol }); } } } } } } |
Solution 2 (DFS):
Solution 3 (Union find):
Time complexity:
Say the grid's height is h and width is w. The overall time complexity is O(hw).
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 | public class Solution { private final int[][] DIRECTIONS = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } }; public int numIslands(char[][] grid) { int count = 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[i].length; j++) { if (grid[i][j] == '1') { dfs(grid, i, j); count++; } } } return count; } private void dfs(char[][] grid, int row, int column) { grid[row][column] = '0'; for (int i = 0; i < 4; i++) { int newRow = row + DIRECTIONS[i][0]; int newColumn = column + DIRECTIONS[i][1]; if (newRow >= 0 && newRow < grid.length && newColumn >= 0 && newColumn < grid[0].length) { if (grid[newRow][newColumn] == '1') { dfs(grid, newRow, newColumn); } } } } } |
Solution 3 (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 | class Solution { private int count = 0; private int[] parent; private int[] size; public int numIslands(char[][] grid) { int h = grid.length; if (h == 0) { return 0; } int w = grid[0].length; parent = new int[h * w]; size = new int[h * w]; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (grid[i][j] == '1') { int index = i * w + j; parent[index] = index; size[index] = 1; count++; if (j > 0 && grid[i][j - 1] == '1') { int neighbor = index - 1; union(index, neighbor); } if (i > 0 && grid[i - 1][j] == '1') { int neighbor = index - w; union(index, neighbor); } } } } return count; } private void union(int a, int b) { int p1 = find(a); int p2 = find(b); if (p1 == p2) { return; } if (size[p1] > size[p2]) { parent[p2] = p1; size[p1] += size[p2]; } else { parent[p1] = p2; size[p2] += size[p1]; } count--; } private int find(int i) { while (i != parent[i]) { parent[i] = parent[parent[i]]; i = parent[i]; } return i; } } |
Time complexity:
Say the grid's height is h and width is w. The overall time complexity is O(hw).
Comments
Post a Comment