[200. Number of Islands](https://leetcode.com/problems/number-of-islands/)

--- tags: leetcode --- # [200. Number of Islands](https://leetcode.com/problems/number-of-islands/) --- # My Solution ## Solution 1: DFS ### The Key Idea for Solving This Coding Question ### C++ Code ```cpp= #define WHITE (0) #define GRAY (1) #define BLACK (2) #define LAND ('1') #define WATER ('0') class Solution { public: int numIslands(vector<vector<char>> &grid) { int rows = grid.size(), cols = grid[0].size(); vector<vector<int>> state(rows, vector<int>(cols, WHITE)); int islandCnt = 0; for (int r = 0; r < rows; ++r) { for (int c = 0; c < cols; ++c) { if (state[r][c] == WHITE && grid[r][c] == LAND) { dfs(grid, state, r, c, rows, cols); ++islandCnt; } } } return islandCnt; } private: void dfs(vector<vector<char>> &grid, vector<vector<int>> &state, int r, int c, int rows, int cols) { if (r < 0 || rows <= r || c < 0 || cols <= c || state[r][c] != WHITE || grid[r][c] != LAND) { return; } state[r][c] = GRAY; dfs(grid, state, r - 1, c, rows, cols); dfs(grid, state, r + 1, c, rows, cols); dfs(grid, state, r, c - 1, rows, cols); dfs(grid, state, r, c + 1, rows, cols); state[r][c] = BLACK; } }; ``` ### Time Complexity ### Space Complexity ## Solution 2: BFS ### The Key Idea for Solving This Coding Question ### C++ Code ```cpp= #define WHITE (0) #define GRAY (1) #define BLACK (2) #define LAND ('1') #define WATER ('0') struct cell { int r; int c; cell(int r, int c) : r(r), c(c) {} }; class Solution { public: int numIslands(vector<vector<char>> &grid) { int rows = grid.size(), cols = grid[0].size(); vector<vector<int>> state(rows, vector<int>(cols, WHITE)); int islandCnt = 0; for (int r = 0; r < rows; ++r) { for (int c = 0; c < cols; ++c) { if (state[r][c] == WHITE && grid[r][c] == LAND) { bfs(grid, state, r, c, rows, cols); ++islandCnt; } } } return islandCnt; } private: void bfs(vector<vector<char>> &grid, vector<vector<int>> &state, int r, int c, int rows, int cols) { queue<cell> q; vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; q.push(cell(r, c)); state[r][c] = GRAY; while (!q.empty()) { int qLen = q.size(); for (int i = 0; i < qLen; ++i) { cell curr = q.front(); q.pop(); for (auto &dir : dirs) { int nextR = curr.r + dir[0], nextC = curr.c + dir[1]; if (nextR < 0 || rows <= nextR || nextC < 0 || cols <= nextC || state[nextR][nextC] != WHITE || grid[nextR][nextC] != LAND) { continue; } q.push(cell(nextR, nextC)); state[nextR][nextC] = GRAY; } state[r][c] = BLACK; } } } }; ``` ### Time Complexity ### Space Complexity ## Solution 3: Union Find ### The Key Idea for Solving This Coding Question ### C++ Code ```cpp= #define LAND ('1') #define WATER ('0') class UnionFind { public: UnionFind(int rows, int cols) { groups = rows * cols; rank.resize(groups, 0); root.resize(groups); for (int i = 0; i < groups; ++i) { root[i] = i; } } int find(int x) { if (x == root[x]) { return x; } return root[x] = find(root[x]); } void unify(int x, int y) { int rootX = find(x), rootY = find(y); if (rootX != rootY) { if (rank[rootX] < rank[rootY]) { root[rootX] = rootY; } else if (rank[rootY] < rank[rootX]) { root[rootY] = rootX; } else { // rank[rootX] == rank[rootY] root[rootY] = rootX; ++rank[rootX]; } --groups; } } int getGroups() { return groups; } private: int groups; vector<int> root; vector<int> rank; }; class Solution { public: int numIslands(vector<vector<char>> &grid) { int rows = grid.size(), cols = grid[0].size(), waterCnt = 0;; UnionFind uf(rows, cols); for (int r = 0; r < rows; ++r) { for (int c = 0; c < cols; ++c) { if (grid[r][c] == WATER) { ++waterCnt; continue; } if (0 <= r - 1 && grid[r - 1][c] == LAND) { uf.unify(getId(r, c, cols), getId(r - 1, c, cols)); } if (r + 1 < rows && grid[r + 1][c] == LAND) { uf.unify(getId(r, c, cols), getId(r + 1, c, cols)); } if (0 <= c - 1 && grid[r][c - 1] == LAND) { uf.unify(getId(r, c, cols), getId(r, c - 1, cols)); } if (c + 1 < cols && grid[r][c + 1] == LAND) { uf.unify(getId(r, c, cols), getId(r, c + 1, cols)); } } } return uf.getGroups() - waterCnt; } private: int getId(int r, int c, int cols) { return r * cols + c; } }; ``` ### Time Complexity ### Space Complexity # Miscellaneous