Command Palette

Search for a command to run...

Hectal
Problem 22.1 · Depth-First SearchMedium

Number of Islands

PatternGraph DFS and Flood FillGraph BFSUnion-FindMatrix Traversal

What it teaches: Counting connected components on a grid by sinking each island.

Practise it on judges as “Number of Islands”.

The problem

Given a grid of '1' (land) and '0' (water), count the islands. Land connects up, down, left and right.

Example 1

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

  • 1 ≤ rows, cols ≤ 300

Pattern clues in the wording

  • → Count connected groups on a grid

These clues point to Graph DFS and Flood Fill: Go as deep as possible from a node, marking visited cells or nodes, to find connected regions.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public int numIslands(char[][] grid) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
1
2
grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
3

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. DFS sinking · O(rows × cols)2. BFS · O(rows × cols)
1

DFS sinking

Time O(rows × cols) Space O(rows × cols) recursion worst case

For each '1', count++ and DFS turning connected '1's into '0's.

Approach 1
class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for (int r = 0; r < grid.length; r++)
            for (int c = 0; c < grid[0].length; c++)
                if (grid[r][c] == '1') { count++; sink(grid, r, c); }
        return count;
    }

    private void sink(char[][] g, int r, int c) {
        if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != '1') return;
        g[r][c] = '0';
        sink(g, r + 1, c); sink(g, r - 1, c); sink(g, r, c + 1); sink(g, r, c - 1);
    }
}

Verdict: Simple and standard.

2

BFS

Time O(rows × cols) Space O(min(rows, cols)) queue typically

Same outer loop; flood each island with a queue instead of recursion.

Approach 2
import java.util.*;

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 r = 0; r < m; r++)
            for (int c = 0; c < n; c++) {
                if (grid[r][c] != '1') continue;
                count++;
                grid[r][c] = '0';
                Deque<int[]> q = new ArrayDeque<>();
                q.offer(new int[]{r, c});
                while (!q.isEmpty()) {
                    int[] cell = q.poll();
                    for (int[] d : dirs) {
                        int nr = cell[0] + d[0], nc = cell[1] + d[1];
                        if (nr < 0 || nc < 0 || nr >= m || nc >= n || grid[nr][nc] != '1') continue;
                        grid[nr][nc] = '0';
                        q.offer(new int[]{nr, nc});
                    }
                }
            }
        return count;
    }
}

Verdict: No deep recursion.

Before you submit

Edge cases and common mistakes

Test these inputs

  • All water
  • All land (one island)
  • Long snake-shaped island (deep recursion)

Mistakes people make

  • Modifying the input when the caller needs it intact (use a visited array instead).

Interview

Follow-up questions

What if land is added one cell at a time and you report the count after each (Number of Islands II)?