Classic Interview 150 P200 Number of Islands

---

Timeline

Timeline

2025-11-03

init

DFS

---

Problem:

P200 Number of Islands

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

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

#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 cause the same node may be pushed onto the stack multiple times Therefore, it is better to mark visited as already pushed onto the stack.

#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 the 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;
        }
};