Log inSign up
mediumLeetCodeNot Started

Number of Islands

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.

Graph
Solve on LeetCode
Lesson

Problem Statement

### Problem Statement

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

---

### Examples

Example 1: ``text 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: ``text 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 - m == grid.length - n == grid[i].length - 1 <= m, n <= 300 - grid[i][j] is '0' or '1'.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Model 2D matrix grids as undirected graphs with 4-directional adjacency.
  • Master the in-place sinking technique to achieve O(1) auxiliary space.
  • Formulate grid problems using Disjoint Set Union (Union-Find).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Count connected components on a 2D binary grid
  • Grouping adjacent cells with identical values
  • Perimeter or area analysis of clustered cells

Algorithmic Decision Tree:

  • If in-place modification of the grid is permitted -> Use In-Place Sinking DFS for O(1) auxiliary space.
  • If grid cannot be modified -> Use BFS with queue or DSU with coordinate flattening.

Connected Patterns:

Max Area of IslandSurrounded RegionsNumber of Provinces

1. BFS with Queue and Visited Matrix

Intuition

Preserves the input grid immutably by maintaining an explicit boolean visited matrix. BFS explores the component layer by layer using a FIFO queue.

Algorithm

  1. Initialize m x n boolean visited array to false.
  2. Initialize islandCount = 0.
  3. Loop r from 0 to m-1 and c from 0 to n-1:
  4. If grid[r][c] == 1 and !visited[r][c]:
  5. islandCount++.
  6. Enqueue (r, c) and mark visited[r][c] = true.
  7. While queue is not empty:
  8. Pop (currR, currC).
  9. For 4 directions (dr, dc):
  10. nr = currR + dr, nc = currC + dc.
  11. If in bounds, grid[nr][nc] == 1, and !visited[nr][nc]:
  12. Mark visited[nr][nc] = true, push (nr, nc) into queue.
  13. Return islandCount.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5class Solution {
6public:
7 int numIslands(std::vector<std::vector<char>>& grid) {
8 if (grid.empty()) return 0;
9 int m = grid.size();
10 int n = grid[0].size();
11 std::vector<std::vector<bool>> visited(m, std::vector<bool>(n, false));
12 int count = 0;
13
14 int dr[] = {-1, 1, 0, 0};
15 int dc[] = {0, 0, -1, 1};
16
17 for (int i = 0; i < m; ++i) {
18 for (int j = 0; j < n; ++j) {
19 if (grid[i][j] == '1' && !visited[i][j]) {
20 count++;
21 std::queue<std::pair<int, int>> q;
22 q.push({i, j});
23 visited[i][j] = true;
24
25 while (!q.empty()) {
26 auto [r, c] = q.front();
27 q.pop();
28
29 for (int k = 0; k < 4; ++k) {
30 int nr = r + dr[k];
31 int nc = c + dc[k];
32 if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == '1' && !visited[nr][nc]) {
33 visited[nr][nc] = true;
34 q.push({nr, nc});
35 }
36 }
37 }
38 }
39 }
40 }
41 return count;
42 }
43};
44
45int main() {
46 Solution sol;
47 std::vector<std::vector<char>> grid = {
48 {'1', '1', '0', '0', '0'},
49 {'1', '1', '0', '0', '0'},
50 {'0', '0', '1', '0', '0'},
51 {'0', '0', '0', '1', '1'}
52 };
53 std::cout << "BFS Islands Count: " << sol.numIslands(grid) << " (Expected: 3)\n";
54 return 0;
55}

Time & Space Complexity

  • Time complexity: O(m * n)
  • Space complexity: O(m * n)

2. Disjoint Set Union (DSU / Union-Find)

Intuition

Treat each land cell as a disjoint set element. When an adjacent neighbor is also land, union the two sets and decrement the component count. Dynamic and supports stream updates.

Algorithm

  1. Initialize DSU with m * n elements and total islands = count of 1s.
  2. Iterate through every cell (r, c):
  3. If grid[r][c] == 1:
  4. Check right neighbor (r, c + 1) and down neighbor (r + 1, c):
  5. If neighbor is also 1:
  6. Union(r * n + c, nr * n + nc).
  7. Return the remaining count of disjoint land sets.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class DSU {
5 std::vector<int> parent, rank;
6 int count;
7public:
8 DSU(int n) : parent(n), rank(n, 0), count(0) {
9 for (int i = 0; i < n; ++i) parent[i] = i;
10 }
11 void incrementCount() { count++; }
12 int getCount() const { return count; }
13 int find(int i) {
14 if (parent[i] == i) return i;
15 return parent[i] = find(parent[i]);
16 }
17 void unite(int i, int j) {
18 int rootI = find(i);
19 int rootJ = find(j);
20 if (rootI != rootJ) {
21 if (rank[rootI] < rank[rootJ]) std::swap(rootI, rootJ);
22 parent[rootJ] = rootI;
23 if (rank[rootI] == rank[rootJ]) rank[rootI]++;
24 count--;
25 }
26 }
27};
28
29class Solution {
30public:
31 int numIslands(std::vector<std::vector<char>>& grid) {
32 if (grid.empty()) return 0;
33 int m = grid.size();
34 int n = grid[0].size();
35 DSU dsu(m * n);
36
37 for (int i = 0; i < m; ++i) {
38 for (int j = 0; j < n; ++j) {
39 if (grid[i][j] == '1') {
40 dsu.incrementCount();
41 }
42 }
43 }
44
45 for (int i = 0; i < m; ++i) {
46 for (int j = 0; j < n; ++j) {
47 if (grid[i][j] == '1') {
48 if (i + 1 < m && grid[i + 1][j] == '1') {
49 dsu.unite(i * n + j, (i + 1) * n + j);
50 }
51 if (j + 1 < n && grid[i][j + 1] == '1') {
52 dsu.unite(i * n + j, i * n + (j + 1));
53 }
54 }
55 }
56 }
57 return dsu.getCount();
58 }
59};
60
61int main() {
62 Solution sol;
63 std::vector<std::vector<char>> grid = {
64 {'1', '1', '0', '0', '0'},
65 {'1', '1', '0', '0', '0'},
66 {'0', '0', '1', '0', '0'},
67 {'0', '0', '0', '1', '1'}
68 };
69 std::cout << "DSU Islands Count: " << sol.numIslands(grid) << " (Expected: 3)\n";
70 return 0;
71}

Time & Space Complexity

  • Time complexity: O(m * n * alpha(m * n))
  • Space complexity: O(m * n)

3. In-Place Sinking DFS (Canonical)

Intuition

Instead of allocating visited tables, directly sink visited land cells to 0. Once converted to water, they are never re-visited by subsequent DFS calls, achieving true O(1) auxiliary space.

Algorithm

  1. Initialize islandCount = 0.
  2. Loop r from 0 to m - 1 and c from 0 to n - 1:
  3. If grid[r][c] == 1:
  4. islandCount++.
  5. Call sinkDfs(r, c).
  6. Define sinkDfs(r, c):
  7. If r < 0 or r >= m or c < 0 or c >= n or grid[r][c] != 1: return.
  8. Set grid[r][c] = 0 (sink the land).
  9. Recursively call sinkDfs on (r-1, c), (r+1, c), (r, c-1), (r, c+1).
  10. Return islandCount.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5 void sink(std::vector<std::vector<char>>& grid, int r, int c) {
6 int m = grid.size();
7 int n = grid[0].size();
8 if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] != '1') {
9 return;
10 }
11
12 grid[r][c] = '0'; // Sink land
13
14 sink(grid, r - 1, c);
15 sink(grid, r + 1, c);
16 sink(grid, r, c - 1);
17 sink(grid, r, c + 1);
18 }
19public:
20 int numIslands(std::vector<std::vector<char>>& grid) {
21 if (grid.empty()) return 0;
22 int m = grid.size();
23 int n = grid[0].size();
24 int count = 0;
25
26 for (int i = 0; i < m; ++i) {
27 for (int j = 0; j < n; ++j) {
28 if (grid[i][j] == '1') {
29 count++;
30 sink(grid, i, j);
31 }
32 }
33 }
34 return count;
35 }
36};
37
38int main() {
39 Solution sol;
40 std::vector<std::vector<char>> grid = {
41 {'1', '1', '0', '0', '0'},
42 {'1', '1', '0', '0', '0'},
43 {'0', '0', '1', '0', '0'},
44 {'0', '0', '0', '1', '1'}
45 };
46 std::cout << "Sinking DFS Islands Count: " << sol.numIslands(grid) << " (Expected: 3)\n";
47 return 0;
48}

Time & Space Complexity

  • Time complexity: O(m * n)
  • Space complexity: O(m * n)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.BFS with Queue & Visited MatrixO(m * n)O(m * n)FIFO queue coordinates expansion without mutating input grid.Queue and matrix allocations
2.Disjoint Set Union (DSU)O(m * n * alpha(m * n))O(m * n)Flattens 2D to 1D and merges adjacent land roots.Rank and parent array maintenance
3.In-Place Sinking DFS (Canonical)OptimalO(m * n)O(m * n)Directly sinks visited 1 to 0 during recursive traversal.Recursion call-stack depth

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Checking 8 directions instead of 4, incorrectly merging diagonal islands.

Pitfall 2:

Not checking boundaries before indexing grid[nr][nc], causing segmentation faults or index errors.

Pitfall 3:

In BFS, forgetting to mark visited upon pushing, leading to queue duplication and Memory Limit Exceeded.

Crucial Edge Cases to Validate:

  • Grid containing only water (all '0's) — Never encounters 1, returns 0 immediately.
  • Grid containing only land (all '1's) — Sinks the entire grid in a single DFS call from (0, 0) and returns 1.
  • Checkerboard pattern of alternating 1s and 0s — Since diagonal lands are not connected, each 1 forms its own independent island of size 1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Ask the interviewer if modifying the input grid is permitted before writing in-place sinking DFS.
  2. If immutability is required, discuss restoring the grid or using a visited array.
  3. Mention that DSU is the standard approach for the follow-up problem 'Number of Islands II' (online dynamic additions).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the In-Place Sinking DFS achieve O(1) auxiliary space (excluding recursion stack)?

2.How are 2D coordinates (r, c) flattened into a 1D index for an m x n grid?

3.Are diagonally adjacent land cells considered part of the same island in this problem?

Back to DSA Sheet