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.

Example 1:

Input: grid = [ [“1”,“1”,“1”,“1”,“0”], [“1”,“1”,“0”,“1”,“0”], [“1”,“1”,“0”,“0”,“0”], [“0”,“0”,“0”,“0”,“0”] ] Output: 1

Example 2:

Input: grid = [ [“1”,“1”,“0”,“0”,“0”], [“1”,“1”,“0”,“0”,“0”], [“0”,“0”,“1”,“0”,“0”], [“0”,“0”,“0”,“1”,“1”] ] Output: 3

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'.

Approach: DFS Flood Fill (Optimal Solution)

Algorithm

1. Iterate through every cell in the grid
2. When a cell with value '1' is found, it starts a new island: increment the count and launch a DFS
3. The DFS marks the current cell as '0' (sinking it) and explores all four neighbors that are still land
4. The DFS terminates when all connected land cells have been sunk, so they are never counted again

Key Insight

Sinking visited land ('1' → '0') eliminates the need for a separate visited matrix. Every '1' that survives to be encountered in the scan marks the start of exactly one distinct island, because all its connected cells were already removed by the DFS.

Time & Space Complexity

• Time Complexity: O(m × n) - every cell is visited at most once
• Space Complexity: O(m × n) - recursion stack in the worst case when the whole grid is one island

Java Implementation

public class NumberOfIslands {

    private char[][] grid;
    private int m;
    private int n;

    public int numIslands(char[][] grid) {
        m = grid.length;
        n = grid[0].length;
        this.grid = grid;
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    dfs(i, j);
                    ans++;
                }
            }
        }
        return ans;
    }

    private void dfs(int i, int j) {
        grid[i][j] = '0'; // sink the visited land
        int[] dirs = {-1, 0, 1, 0, -1};
        for (int k = 0; k < 4; k++) {
            int x = i + dirs[k];
            int y = j + dirs[k + 1];
            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {
                dfs(x, y);
            }
        }
    }
}

Example Walkthrough

For grid from example 2:

1. Scan row 0: find (0,0) land → island count 1, DFS sinks (0,0),(0,1),(1,0),(1,1)
2. Continue scanning, row 2: find (2,2) land → island count 2, DFS sinks it
3. Row 3: find (3,3) land → island count 3, DFS sinks (3,3),(3,4)
4. No more land cells → return 3

Alternative Approach: BFS

import java.util.ArrayDeque;
import java.util.Deque;

public class NumberOfIslandsBfs {

    public int numIslands(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        int ans = 0;
        int[] dirs = {-1, 0, 1, 0, -1};
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    ans++;
                    grid[i][j] = '0';
                    Deque<int[]> q = new ArrayDeque<>();
                    q.offer(new int[] {i, j});
                    while (!q.isEmpty()) {
                        int[] cell = q.poll();
                        for (int k = 0; k < 4; k++) {
                            int x = cell[0] + dirs[k];
                            int y = cell[1] + dirs[k + 1];
                            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {
                                grid[x][y] = '0';
                                q.offer(new int[] {x, y});
                            }
                        }
                    }
                }
            }
        }
        return ans;
    }
}

The BFS variant uses an explicit queue instead of the recursion stack, giving the same O(m × n) time with O(m × n) queue space.

Alternative Approach: Union-Find

A Union-Find solution treats each land cell as a set, unions horizontally/vertically adjacent land cells, then counts the distinct roots among land cells. It runs in O(m × n × α) time with O(m × n) space.

Key Insights

1. In-place Sinking: Mutating '1' to '0' removes the need for a visited array
2. Four Directions: Only horizontal and vertical adjacency count — diagonals do not
3. Count on Discovery: Every unvisited '1' is the first cell of a new island
4. Edge Safety: Bounds checks prevent out-of-range accesses during exploration

The DFS flood-fill approach is the optimal solution, providing O(m × n) time and O(m × n) space.