> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/graph_search/number_of_islands.md). # 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\`。 1. 建立UnionFind的parent\[] (或者 parent hashmap)，初始化各个`parent[i * N + j] = i * N + j`，如果`grid[i][j] == true`，则岛屿计数count++ 2. 之后再对矩阵遍历一次，当遇到岛屿时，则要检查上下左右四个方向的邻近点，如果也是岛屿则合并，并且count--； Union Find结构可以用Path Compression和Weighted Union进行优化。 ## Solution DFS (3ms AC) ```java 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) ```java 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) ```java 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 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) ```java 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 qx = new LinkedList(); Queue qy = new LinkedList(); 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) ```java 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) ```java 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 * [programcreek: LeetCode – Number of Islands (Java)](http://www.programcreek.com/2014/04/leetcode-number-of-islands-java/) * [LeetCode Discussion: AC Java Solution using Union-Find with explanations](https://discuss.leetcode.com/topic/11969/ac-java-solution-using-union-find-with-explanations) --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://aaronice.gitbook.io/lintcode/graph_search/number_of_islands.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.