Number of Islands

Problem Statement

Given an m × n 2D binary grid grid, where:

'1' represents land
'0' represents water

Return the number of islands. An island is defined as a group of adjacent lands connected horizontally or vertically, and all edges of the grid are surrounded by water.

Examples

Example 1

Input:
[
  ["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:
[
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

Constraints

Grid size: m × n, typically up to 300×300.
Each cell is '0' or '1'.
Edges are always water (no wrap-around).
Total cells visited ≤ m × n.

Intuition

We treat the grid as a graph:

Each land cell '1' is a node.
Nodes are connected if they are adjacent (up/down/left/right).
The task is to count connected components.

When you encounter a '1' that hasn't been visited, start a graph traversal to mark all reachable land cells, and increment the island count.

This can be done through:

DFS (depth-first search)
BFS (breadth-first search)
Union-Find (disjoint set union)

Approach 1: DFS (Depth-First Search)

Algorithm

Initialize counter count = 0.
Loop through every cell (i, j):
- If grid[i][j] == '1':
  - Call dfs(i, j) to mark all connected land.
  - Increment count.
Return count.

DFS marks visited land by changing '1' → '0' (in-place) or using a separate visited array.

Java Code (In-place Modification)

class Solution {
    public int numIslands(char[][] grid) {
        int m = grid.length, n = grid[0].length, count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }
    private void dfs(char[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') {
            return;
        }
        grid[i][j] = '0';
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }
}

Dry Run

grid = [
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1']
]

count=0
At (0,0): found '1', DFS clears connected region:
visits (0,0)->(0,1),(1,0),(1,1), marking them '0'.
→ count = 1
Next islands found at (2,2) and (3,3), each clearing region:
→ count becomes 3
Final result: 3

Complexity (DFS)

Metric	Value
Time Complexity	O(m × n)
Space Complexity	O(m × n) stack (worst-case recursion)

All cells are visited once, and each DFS explores connected neighbors.

Approach 2: BFS (Breadth-First Search)

Algorithm

Similar to DFS, but uses a queue to explore connected land layer by layer.

Java Code

class Solution {
    public int numIslands(char[][] grid) {
        int m = grid.length, n = grid[0].length, count = 0;
        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    grid[i][j] = '0';
                    Queue<int[]> q = new LinkedList<>();
                    q.add(new int[]{i,j});
                    while (!q.isEmpty()) {
                        int[] cur = q.poll();
                        for (int[] d : dirs) {
                            int ni = cur[0] + d[0], nj = cur[1] + d[1];
                            if (ni>=0 && ni<m && nj>=0 && nj<n && grid[ni][nj]=='1') {
                                grid[ni][nj] = '0';
                                q.add(new int[]{ni,nj});
                            }
                        }
                    }
                }
            }
        }
        return count;
    }
}

Complexity (BFS)

Metric	Value
Time Complexity	O(m × n)
Space Complexity	O(m × n) in queue (max)

Optional: Union-Find (Disjoint Set)

This method builds a union-find structure over cells, merging adjacent lands. After processing, the number of unique roots = island count. Best when dynamic updates are needed.

Applications

Discovering land mass count in geographical data.
Counting disconnected clusters in image processing.
Modeling connectivity in networks or clusters.
Simulating spread in epidemiology models.

Summary

Problem: Count connected components (islands) in 2D grid.
Common approaches: DFS, BFS, Union-Find.
Time complexity: O(m × n).
Space complexity: O(m × n) worst-case recursion or queue.
DFS and BFS are both widely accepted and easy to implement.