Number of Islands

MediumGraphDFSBFSMatrix
Category: Graphs
Companies that ask this question:
AmazonFacebookGoogleMicrosoftBloomberg

Approach

Number of Islands

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:

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

Constraints

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

Approach

Key Insight

This is a Connected Components problem!

Each island is a connected component of '1's. We can:

  1. Scan the grid for unvisited '1's
  2. When found, increment island count
  3. Use DFS/BFS to mark entire island as visited

Solution 1: DFS (Depth-First Search)

Recursively explore all connected land cells.

Algorithm:

  1. Initialize island count = 0
  2. For each cell in grid:
    • If cell is '1' (unvisited land):
      • Increment island count
      • DFS to mark entire island as visited
  3. DFS function:
    • Mark current cell as '0' (visited)
    • Recursively visit all 4 neighbors

Solution 2: BFS (Breadth-First Search)

Iteratively explore using a queue.

Algorithm:

  1. Initialize island count = 0
  2. For each cell in grid:
    • If cell is '1':
      • Increment island count
      • BFS to mark entire island
  3. BFS function:
    • Add cell to queue
    • While queue not empty:
      • Visit cell, mark as '0'
      • Add unvisited land neighbors to queue

Solution 3: Union-Find

Treat as disjoint set problem.

Algorithm:

  1. Initialize each land cell as separate set
  2. Union adjacent land cells
  3. Count number of disjoint sets

Complexity Analysis

DFS/BFS Solution:

  • Time Complexity: O(m × n) - visit each cell once
  • Space Complexity: O(m × n) - worst case recursion depth or queue size

Union-Find:

  • Time Complexity: O(m × n × α(m×n)) - α is inverse Ackermann
  • Space Complexity: O(m × n) - parent and rank arrays

Pattern Recognition

This problem demonstrates:

  • Connected Components in 2D grid
  • Graph Traversal (DFS/BFS)
  • In-place modification technique
  • Matrix navigation with 4 directions
  • Foundation for similar grid problems

Solution

java
1import java.util.*;
2
3class Solution {
4    // Solution 1: DFS (Depth-First Search)
5    public int numIslands(char[][] grid) {
6        if (grid == null || grid.length == 0) return 0;
7
8        int m = grid.length;
9        int n = grid[0].length;
10        int islandCount = 0;
11
12        for (int i = 0; i < m; i++) {
13            for (int j = 0; j < n; j++) {
14                if (grid[i][j] == '1') {
15                    islandCount++;
16                    dfs(grid, i, j);
17                }
18            }
19        }
20
21        return islandCount;
22    }
23
24    private void dfs(char[][] grid, int row, int col) {
25        int m = grid.length;
26        int n = grid[0].length;
27
28        // Boundary check and water check
29        if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] == '0') {
30            return;
31        }
32
33        // Mark as visited
34        grid[row][col] = '0';
35
36        // Explore all 4 directions
37        dfs(grid, row + 1, col);  // down
38        dfs(grid, row - 1, col);  // up
39        dfs(grid, row, col + 1);  // right
40        dfs(grid, row, col - 1);  // left
41    }
42
43    // Solution 2: BFS (Breadth-First Search)
44    public int numIslandsBFS(char[][] grid) {
45        if (grid == null || grid.length == 0) return 0;
46
47        int m = grid.length;
48        int n = grid[0].length;
49        int islandCount = 0;
50
51        for (int i = 0; i < m; i++) {
52            for (int j = 0; j < n; j++) {
53                if (grid[i][j] == '1') {
54                    islandCount++;
55                    bfs(grid, i, j);
56                }
57            }
58        }
59
60        return islandCount;
61    }
62
63    private void bfs(char[][] grid, int startRow, int startCol) {
64        int m = grid.length;
65        int n = grid[0].length;
66
67        Queue<int[]> queue = new LinkedList<>();
68        queue.offer(new int[]{startRow, startCol});
69        grid[startRow][startCol] = '0';
70
71        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
72
73        while (!queue.isEmpty()) {
74            int[] cell = queue.poll();
75            int row = cell[0];
76            int col = cell[1];
77
78            for (int[] dir : directions) {
79                int nr = row + dir[0];
80                int nc = col + dir[1];
81
82                if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == '1') {
83                    grid[nr][nc] = '0';
84                    queue.offer(new int[]{nr, nc});
85                }
86            }
87        }
88    }
89
90    // Solution 3: Union-Find
91    class UnionFind {
92        int[] parent;
93        int[] rank;
94        int count;
95
96        public UnionFind(char[][] grid) {
97            int m = grid.length;
98            int n = grid[0].length;
99            parent = new int[m * n];
100            rank = new int[m * n];
101            count = 0;
102
103            for (int i = 0; i < m; i++) {
104                for (int j = 0; j < n; j++) {
105                    if (grid[i][j] == '1') {
106                        int id = i * n + j;
107                        parent[id] = id;
108                        count++;
109                    }
110                }
111            }
112        }
113
114        public int find(int x) {
115            if (parent[x] != x) {
116                parent[x] = find(parent[x]);
117            }
118            return parent[x];
119        }
120
121        public void union(int x, int y) {
122            int rootX = find(x);
123            int rootY = find(y);
124
125            if (rootX != rootY) {
126                if (rank[rootX] > rank[rootY]) {
127                    parent[rootY] = rootX;
128                } else if (rank[rootX] < rank[rootY]) {
129                    parent[rootX] = rootY;
130                } else {
131                    parent[rootY] = rootX;
132                    rank[rootX]++;
133                }
134                count--;
135            }
136        }
137
138        public int getCount() {
139            return count;
140        }
141    }
142
143    public int numIslandsUnionFind(char[][] grid) {
144        if (grid == null || grid.length == 0) return 0;
145
146        int m = grid.length;
147        int n = grid[0].length;
148        UnionFind uf = new UnionFind(grid);
149
150        for (int i = 0; i < m; i++) {
151            for (int j = 0; j < n; j++) {
152                if (grid[i][j] == '1') {
153                    int id = i * n + j;
154                    // Union with right neighbor
155                    if (j + 1 < n && grid[i][j + 1] == '1') {
156                        uf.union(id, id + 1);
157                    }
158                    // Union with bottom neighbor
159                    if (i + 1 < m && grid[i + 1][j] == '1') {
160                        uf.union(id, id + n);
161                    }
162                }
163            }
164        }
165
166        return uf.getCount();
167    }
168}
169
Loading visualizer...