LeetCode 200. Number of Islands

Posted on In , Views:

🧩 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 formed by connecting adjacent lands horizontally or vertically.
You may assume all four edges of the grid are surrounded by water.

💬 Examples

Example 1

1
2
3
4
5
6
7
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

1
2
3
4
5
6
7
Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

💡 Intuition

This is a connected components counting problem on a grid.

  • Each '1' is land.
  • We can run DFS or BFS from every unvisited '1'.
  • Every time we start a new search, it means we found a new island.
  • Mark visited cells as '0' to avoid double counting.

🔢 Java Code (DFS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    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') {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }

    private void dfs(char[][] grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') {
            return;
        }
        grid[i][j] = '0'; // mark visited
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }
}

🔄 Alternative Approaches

  • BFS with Queue instead of recursion.
  • Union-Find (Disjoint Set Union): Treat each land cell as a node, union adjacent lands, then count distinct sets.

⏱ Time and Space Complexity

  • Time Complexity: O(m × n) — each cell is visited at most once.
  • Space Complexity:
    • O(m × n) worst-case recursion depth (DFS stack).
    • O(min(m, n)) for BFS queue.
    • Union-Find requires O(m × n) extra memory.

✍️ Summary

  • Classic flood fill problem.
  • Each DFS/BFS call explores one island fully.
  • Count how many times we start a new DFS/BFS.

Related problems

  • lc-695 — Max Area of Island
  • lc-463 — Island Perimeter
  • lc-733 — Flood Fill