Number of Islands

Link

Description

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.

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'.

Solution

DFS

class Solution {
private:
    int n, m;
    void dfs(vector<vector<char>>& grid, int x, int y) {
        if (x < 0 || x >= n || y < 0 || y >= m) return;
        if (grid[x][y] == '0') return;
        grid[x][y] = '0';
        dfs(grid, x + 1, y);
        dfs(grid, x, y + 1);
        dfs(grid, x - 1, y);
        dfs(grid, x, y - 1);
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        int res = 0;
        n = grid.size(), m = grid[0].size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '1') {
                    res++;
                    dfs(grid, i, j);
                }
            }
        }
        return res;
    }
};

See reference (Chinese).

• Time complexity: \(O(nm)\);
• Space complexity: \(O(nm)\).

BFS

class Solution {
private:
    int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
    int m, n;
    void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
        queue<pair<int, int>> q;
        q.emplace(x, y);
        visited[x][y] = true;

        while (!q.empty()) {
            auto curr = q.front(); q.pop();
            int currX = curr.first, currY = curr.second;
            for (int i = 0; i < 4; i++) {
                int nextX = currX + dx[i], nextY = currY + dy[i];
                if (nextX < 0 || nextX >= m || nextY < 0 || nextY >= n) continue;
                if (!visited[nextX][nextY] && grid[nextX][nextY] == '1') {
                    q.emplace(nextX, nextY);
                    visited[nextX][nextY] = true;
                }
            }
        }
    }

public:
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size(); n = grid[0].size();
        vector<vector<bool>> visited = vector<vector<bool>>(m, vector<bool>(n, false));

        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && grid[i][j] == '1') {
                    res++;
                    bfs(grid, visited, i, j);
                }
            }
        }

        return res;
    }
};

Union Find

class Solution {
private:
    vector<int> p;
    int columns;
    int sets;

    void build(vector<vector<char>>& grid, int m, int n) {
        columns = n;
        sets = 0;
        p = vector<int>(m * n + 1, 0);

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    int idx = index(i, j);
                    p[idx] = idx;
                    sets++;
                }
            }
        }
    }

    int find(int i) {
        if (i != p[i]) p[i] = find(p[i]);
        return p[i];
    }

    void unionSets(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx != fy) {
            p[fx] = fy;
            sets--;
        }
    }

    int index(int a, int b) const {
        return a * columns + b;
    }

public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        build(grid, m, n);

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    if (j > 0 && grid[i][j - 1] == '1')
                        unionSets(index(i, j), index(i, j - 1));
                    if (i > 0 && grid[i - 1][j] == '1')
                        unionSets(index(i, j), index(i - 1, j));
                }
            }
        }

        return sets;
    }
};

Breakdown:

1. Data Structures:
2. vector<int> p;: Parent array for Union-Find, where p[i] represents the parent of element i.
3. int columns;: Stores the number of columns in the grid to convert 2D indices into 1D.
4. int sets;: Tracks the number of disjoint sets (islands).
5. Build Function:
6. Initializes the parent array p for each cell in the grid that is land ('1'). Each land cell is initially its own parent, indicating a separate island.
7. The sets variable is incremented for each land cell, assuming each cell is an isolated island initially.
8. Find Function:
9. Implements path compression for efficient finds. If an element's parent is not itself, it recursively finds the ultimate parent and updates the parent to point directly to the ultimate parent, reducing future find times.
10. UnionSets Function:
11. Merges two sets (islands) into one by connecting their roots. If the roots are different, it sets one root to be the parent of the other, effectively merging the two sets. It decrements the sets counter since two islands merge into one.
12. Index Function:
13. Converts 2D grid coordinates to a 1D index. This is necessary because the Union-Find structure is represented as a 1D array.
14. numIslands Function:
15. Iterates over the grid, and for each land cell, it tries to union it with its adjacent (up and left, to avoid redundancy) land cells. This step effectively groups adjacent lands into single islands.

Time Complexity:

• Build Function: \(O(MN)\) where \(M\) is the number of rows and \(N\) is the number of columns, as it iterates over all cells.
• Union and Find Operations: Amortized \(O(\alpha(MN))\) for each operation, where \(\alpha\) is the Inverse Ackermann function, which grows extremely slowly and is practically constant for all conceivable problem sizes.
• Total Time Complexity: \(O(MN \times \alpha(MN))\), considering both the initial building phase and the union-find operations for each cell. The actual impact of \(\alpha(MN)\) is so minimal that the time complexity can be considered nearly linear to the input size.

Space Complexity:

• Parent Array \(p\): \(O(MN)\) for storing the parent of each cell.
• Total Space Complexity: \(O(MN)\), as the primary storage is the parent array, with no additional significant storage.