Number of Islands
Given an `m x n` 2D binary grid `grid` which represents a map of `'1'`s (land) and `'0'`s (water), return 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.
Examples
Constraints
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j] is '0' or '1'.
Depth-First Search (DFS)
Approach
We iterate through every cell in the grid. If we find a `'1'`, it means we have found a new island. We increment our island count, and then use DFS to explore all adjacent land connected to this cell. During the DFS, we change visited `'1'`s to `'0'`s so we don't visit them again and count them as separate islands.
Complexity Analysis
Time complexity is O(m * n) because we visit each cell at most a few times. Space complexity is O(m * n) in the worst case for the call stack if the grid is filled with lands.
class Solution { public int numIslands(char[][] grid) { if (grid == null || grid.length == 0) { return 0; } int numIslands = 0; int m = grid.length; int n = grid[0].length; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == '1') { numIslands++; dfs(grid, i, j); } } } return numIslands; } private void dfs(char[][] grid, int r, int c) { int m = grid.length; int n = grid[0].length; // Out of bounds or water if (r < 0 || c < 0 || r >= m || c >= n || grid[r][c] == '0') { return; } // Mark as visited by turning it into water grid[r][c] = '0'; // Explore all 4 adjacent directions dfs(grid, r + 1, c); dfs(grid, r - 1, c); dfs(grid, r, c + 1); dfs(grid, r, c - 1); }}