Number of Islands

Problem Description

You’re given a 2D grid of characters '1' (land) and '0' (water). You need to find the number of islands in the grid.

Rules:

An island is formed by connecting adjacent '1's horizontally or vertically.
Islands are not connected diagonally.
You can assume the grid is surrounded by water (i.e., no need to check for wrap-around at edges).

Example

Input:

[
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1']
]

Output:

Explanation:

Island 1: top-left 2×2 block of '1's
Island 2: the single '1' at (2,2)
Island 3: bottom-right connected '1's at (3,3) and (3,4)

Approach Overview

The problem is fundamentally a graph traversal problem:

Each '1' in the grid is a node.
Connected '1's (up, down, left, right) are edges.
An island is a connected component.

We can solve this using:

Depth-First Search (DFS)
Breadth-First Search (BFS)
Union-Find (Disjoint Set Union) – advanced

We’ll use DFS in this tutorial because it’s intuitive and easy to implement recursively.

High-Level DFS Algorithm

Loop through every cell in the grid.
When you find a '1', it means we’ve discovered a new island.
Increment the island counter.
Use DFS to mark all adjacent land cells connected to it as visited (turn them into '0').
Continue traversing the grid.

DFS Function Details

The DFS function:

Starts from a cell with '1'.
Recursively visits all its connected '1' neighbors (up, down, left, right).
Marks each visited cell as '0' to avoid visiting it again.

Edge Cases

Empty grid
Grid with all '0's
Grid with all '1's
Very large grid (be careful of stack overflow with recursive DFS)

Complete Java Code with Comments

public class NumberOfIslands {

    public int numIslands(char[][] grid) {
        // Handle null or empty input
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int numberOfIslands = 0;
        int rows = grid.length;
        int cols = grid[0].length;

        // Loop through each cell in the grid
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {

                // If the cell is land ('1'), start DFS
                if (grid[i][j] == '1') {
                    numberOfIslands++;     // Found a new island
                    dfs(grid, i, j);       // Mark all land in this island
                }
            }
        }

        return numberOfIslands;
    }

    // Recursive DFS to mark all connected land as visited
    private void dfs(char[][] grid, int i, int j) {
        int rows = grid.length;
        int cols = grid[0].length;

        // Base case: stop recursion if out of bounds or at water
        if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] == '0') {
            return;
        }

        // Mark the current land cell as visited
        grid[i][j] = '0';

        // Recursively visit all 4 adjacent directions
        dfs(grid, i - 1, j); // Up
        dfs(grid, i + 1, j); // Down
        dfs(grid, i, j - 1); // Left
        dfs(grid, i, j + 1); // Right
    }
}

Dry run

Initial State

numberOfIslands = 0
Loop starts from top-left: (i=0, j=0)
Grid size: 4 rows × 5 columns

Dry Run Steps

Step 1: Cell (0,0)

Value: '1'
Not visited before → It’s the start of a new island
numberOfIslands = 1
Call dfs(0,0)

DFS(0,0):

Mark grid[0][0] = '0'
DFS calls:
- dfs(-1, 0) → invalid index → return
- dfs(1, 0) → grid[1][0] = '1' → visit it
- dfs(0, -1) → invalid → return
- dfs(0, 1) → grid[0][1] = '1' → visit it

DFS(1,0):

Mark grid[1][0] = '0'
DFS:
- dfs(0,0) → already '0' → return
- dfs(2,0) → grid[2][0] = '0' → return
- dfs(1,-1) → invalid → return
- dfs(1,1) → grid[1][1] = '1' → visit it

DFS(1,1):

Mark grid[1][1] = '0'
DFS:
- dfs(0,1) → grid[0][1] = '1' → visit it

DFS(0,1):

Mark grid[0][1] = '0'
All neighbors are either '0' or out of bounds → return

Island 1 completely visited.

Grid after Step 1:

Step 2: Cell (0,1) → Already visited (‘0’) → skip

Step 3: Cell (0,2) → Water → skip

Step 4: Cell (0,3) → Water → skip

Step 5: Cell (0,4) → Water → skip

Step 6: Cell (1,0) → Visited → skip

Step 7: Cell (1,1) → Visited → skip

Step 8: Cell (1,2) → Water → skip

Step 9: Cell (1,3) → Water → skip

Step 10: Cell (1,4) → Water → skip

Step 11: Cell (2,0) → Water → skip

Step 12: Cell (2,1) → Water → skip

Step 13: Cell (2,2)

Value: '1' → new island
numberOfIslands = 2
Call dfs(2,2)

DFS(2,2):

Mark grid[2][2] = '0'
All neighbors are '0' or out of bounds → return

Island 2 visited.

Grid after Step 2:

Step 14–16: Cell (2,3) to Cell (2,4) → Water → skip

Step 17–18: Cell (3,0) and (3,1) → Water → skip

Step 19: Cell (3,2) → Water → skip

Step 20: Cell (3,3)

Value: '1' → new island
numberOfIslands = 3
Call dfs(3,3)

DFS(3,3):

Mark grid[3][3] = '0'
Check right → dfs(3,4) → grid[3][4] = '1' → visit

DFS(3,4):

Mark grid[3][4] = '0'
All neighbors are water or out of bounds → return

Island 3 visited.

Final Grid

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

Final Result

numberOfIslands = 3