Skip to main content

Number of Islands

LeetCode 200 | Difficulty: Medium​

Medium

Problem Description​

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 surrounded by water.

Constraints​

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

Examples​

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

Approach​

How DFS Explores an Island​

When we find an unvisited '1', we start DFS to mark all connected land cells as visited. This "sinks" the entire island so we don't count it again.

DFS Expansion on Example 2​

Key Insight: This is a classic connected components problem on a grid. Each island is one connected component of '1's.

Solution: DFS (Recursive)​

DFS Approach — O(m×n)
public class Solution {
    public int NumIslands(char[][] grid) {
        int m = grid.Length;
        int n = grid[0].Length;
        bool[,] visited = new bool[m, n];
        int count = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1' && !visited[i, j]) {
                    MarkDfs(grid, visited, i, j);
                    count++;
                }
            }
        }
        return count;
    }

    private void MarkDfs(char[][] grid, bool[,] visited, int i, int j) {
        if (i < 0 || i >= grid.Length || j < 0 || j >= grid[0].Length
            || visited[i, j] || grid[i][j] == '0')
            return;

        visited[i, j] = true;

        MarkDfs(grid, visited, i - 1, j); // up
        MarkDfs(grid, visited, i + 1, j); // down
        MarkDfs(grid, visited, i, j - 1); // left
        MarkDfs(grid, visited, i, j + 1); // right
    }
}

Solution: BFS (Iterative)​

Use a queue to avoid recursion stack overflow for very large grids.

BFS Approach
public class Solution {
    private readonly int[][] dirs = new int[][] {
        new int[] {-1, 0}, new int[] {1, 0},
        new int[] {0, -1}, new int[] {0, 1}
    };

    public int NumIslands(char[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        int count = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    BFS(grid, i, j, m, n);
                }
            }
        }
        return count;
    }

    private void BFS(char[][] grid, int si, int sj, int m, int n) {
        Queue<(int, int)> queue = new Queue<(int, int)>();
        queue.Enqueue((si, sj));
        grid[si][sj] = '0'; // sink the land
        
        while (queue.Count > 0) {
            var (r, c) = queue.Dequeue();
            
            foreach (var d in dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == '1') {
                    grid[nr][nc] = '0';
                    queue.Enqueue((nr, nc));
                }
            }
        }
    }
}
DFS vs BFS Trade-off
  • DFS — Simpler code, but may hit stack overflow on very large grids ($300 \times 300$)
  • BFS — Iterative, no stack overflow risk, slightly more code
  • Both have the same time/space complexity

Complexity Analysis​

ApproachTimeSpaceNotes
DFS$O(m \times n)$$O(m \times n)$Visited array + recursion stack
BFS$O(m \times n)$$O(\min(m, n))$Queue holds at most one "frontier"
DFS (in-place)$O(m \times n)$$O(m \times n)$Modifies grid, saves visited array

Interview Tips​

Common Variations
  1. "Can you solve it without extra space?" → Modify grid in-place (change '1' to '0' after visiting)
  2. "What about diagonal connections?" → Add 4 more directions to the dirs array
  3. "Count distinct island shapes?" → 694. Number of Distinct Islands — encode DFS path