Cover image for Interview Classic 150 Questions P200 Number of Islands

Interview Classic 150 Questions P200 Number of Islands

(Updated: )
algorithm
, , , ,
Timeline

timeline

2025-11-03

init

DFS

Title:

P200 Number of Islands

https://leetcode.cn/problems/number-of-islands/description/?envType=study-plan-v2&envId=top-interview-150

DFS to determine the number of islands, essentially using DFS to count the number of connected components

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <vector>
#include <utility>
#include <stack>

using std::vector;
using std::pair;
using std::stack;

class Solution {
    public:
	int numIslands(vector<vector<char> > &grid)
	{
		int m = grid.size(), n = grid[0].size();
		vector<vector<bool> > visited =
			vector<vector<bool> >(m, vector<bool>(n, false));
		int island_num = 0;
		int i, j;
		stack<pair<int, int> > st;

		for (i = 0; i < m; i++) {
			for (j = 0; j < n; j++) {
				if (visited[i][j] || grid[i][j] =='0')
					continue;

				st.push({ i, j });
				while (!st.empty()) {
					auto [curr_i, curr_j] = st.top();
					visited[curr_i][curr_j] = true;
					st.pop();
					// up
					if (curr_i - 1 >= 0 &&
					    !visited[curr_i - 1][curr_j] &&
					    grid[curr_i - 1][curr_j] == '1') {
						st.push({ curr_i - 1, curr_j });
					}

					// down
					if (curr_i + 1 < m &&
					    !visited[curr_i + 1][curr_j] &&
					    grid[curr_i + 1][curr_j] == '1') {
						st.push({ curr_i + 1, curr_j });
					}

					// left
					if (curr_j - 1 >= 0 &&
					    !visited[curr_i][curr_j - 1] &&
					    grid[curr_i][curr_j - 1] == '1') {
						st.push({ curr_i, curr_j - 1 });
					}

					// right
					if (curr_j + 1 < n &&
					    !visited[curr_i][curr_j + 1] &&
					    grid[curr_i][curr_j + 1] == '1') {
						st.push({ curr_i, curr_j + 1 });
					}

				}
				island_num ++;
			}
		}

		return island_num;
	}
};

leetcode hot 100 rewrite, found that the previous approach would causethe same node may be pushed onto the stack multiple times, so it’s better to mark visited as already pushed onto the stack.

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <vector>
#include <stack>
#include <utility>

using std::vector;
using std::pair;
using std::stack;

class Solution {
    public:
        int numIslands(vector<vector<char> > &grid)
        {
                // 1 <= m, n <= 300
                int i, j, m = grid.size(), n = grid[0].size();
                vector<vector<bool> > visited(m, vector<bool>(n, false));
                stack<pair<int, int> > stk;
                int nr_island = 0;

                for (i = 0; i < m; i++) {
                        for (j = 0; j < n; j++) {
                                if (visited[i][j] || grid[i][j] == '0')
                                        continue;
                                // DFS
                                stk.push({ i, j });
                                visited[i][j] = true; // Indicates already pushed onto stack

                                while (!stk.empty()) {
                                        auto [ipos, jpos] = stk.top();
                                        stk.pop();

                                        // up
                                        if (ipos - 1 >= 0 && !visited[ipos - 1][jpos] &&
                                            grid[ipos - 1][jpos] == '1') {
                                                stk.push({ ipos - 1, jpos });
                                                visited[ipos - 1][jpos] = true;
                                        }

                                        // down
                                        if (ipos + 1 < m && !visited[ipos + 1][jpos] &&
                                            grid[ipos + 1][jpos] == '1') {
                                                stk.push({ ipos + 1, jpos });
                                                visited[ipos + 1][jpos] = true;
                                        }

                                        // left
                                        if (jpos - 1 >= 0 && !visited[ipos][jpos - 1] &&
                                            grid[ipos][jpos - 1] == '1') {
                                                stk.push({ ipos, jpos - 1 });
                                                visited[ipos][jpos - 1] = true;
                                        }

                                        // right
                                        if (jpos + 1 < n && !visited[ipos][jpos + 1] &&
                                            grid[ipos][jpos + 1] == '1') {
                                                stk.push({ ipos, jpos + 1 });
                                                visited[ipos][jpos + 1] = true;
                                        }
                                }

                                nr_island++;
                        }
                }

                return nr_island;
        }
};