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 2 3 4 5 6 7 8 9 10 11 12 13

Input: 11110 11010 11000 00000 Output: 1

Input: 11000 11000 00100 00011 Output: 3

Analysis

DFS

It is very obvious that this problem can be solved by using an DFS approach.

Note: Be careful of the conditions that we dfs a place, which include boundary check and whether it is an island.

publicintnumIslands(char[][] grid){ if (grid == null || grid.length == 0) { return0; } int m = grid.length; int n = grid[0].length; boolean[][] marked = newboolean[m][n]; // or visit by setting value as '0' int[][] direction = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; int islandCount = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (!marked[i][j] && grid[i][j] == '1') { dfs(i, j, grid, marked, direction); ++islandCount; } } } return islandCount; }

privatevoiddfs(int i, int j, char[][] grid, boolean[][] marked, int[][] direction){ int m = grid.length; int n = grid[0].length; marked[i][j] = true; // visit; for (int[] dir : direction) { int x = i + dir[0]; int y = j + dir[1]; if (x >= 0 && x < m && y >= 0 && y < n) { if (!marked[x][y] && grid[x][y] == '1') { dfs(x, y, grid, marked, direction); } } } }

Time: $O(MN)$ Space: $O(MN)$. If we modify the original grid array, can we reduce the complexity to $O(1)$? No. It is because DFS goes by a call stack.

publicintnumIslands(char[][] grid){ if (grid == null || grid.length == 0) { return0; } int m = grid.length; int n = grid[0].length; boolean[][] marked = newboolean[m][n]; // or visit by setting value as '0' int[][] direction = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; int islandCount = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (!marked[i][j] && grid[i][j] == '1') { bfs(i, j, grid, marked, direction); ++islandCount; } } } return islandCount; }

privatevoidbfs(int i, int j, char[][] grid, boolean[][] marked, int[][] direction){ int m = grid.length; int n = grid[0].length; Queue<int[]> queue = new LinkedList<>(); queue.offer(newint[] { i, j }); marked[i][j] = true; // bfs while (queue.size() > 0) { int[] curr = queue.poll(); for (int[] dir : direction) { int x = curr[0] + dir[0]; int y = curr[1] + dir[1]; if (x >= 0 && x < m && y >= 0 && y < n) { if (!marked[x][y] && grid[x][y] == '1') { queue.offer(newint[] { x, y }); marked[x][y] = true; // mark when enqueued } } } } }

Time: $O(MN)$ Space: $O(\min{(M, N)})$. In the worst case where the grid is filled with lands, the size of queue can be $O(\min{(M, N)})$ as follows.