Blind 75.30 - Number of Islands

Number of islands.

Problem description

Taken directly from LeetCode.

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 type

Just application of graph concepts / BFS / DFS.

Solution

Just looking at the problem name makes me think that I’m counting connected components, which can be done by constructing an adjlist, running BFS on all vertices, and tracking which vertices were seen. Each time you restart BFS is a new connected component.

BFS and DFS are both perfectly fine here. Only question is: is there a way to do this without an \(O(mn)\) memory-costing seen matrix? I don’t think there is.

void bfs(vector<vector<bool>>& seen, vector<vector<char>>& grid, int i, int j) {
    queue<pair<int, int>> q;
    q.push(pair<int, int>(i, j));
    seen[i][j] = true;
    while (!q.empty()) {
        int currentX = q.front().first, currentY = q.front().second;
        q.pop();
        if (currentX > 0 && !seen[currentX - 1][currentY] && grid[currentX - 1][currentY] == '1') {
            q.push(pair<int, int>(currentX - 1, currentY));
            seen[currentX - 1][currentY] = true;
        }
        if (currentX < grid.size() - 1 && !seen[currentX + 1][currentY] && grid[currentX + 1][currentY] == '1') {
            q.push(pair<int, int>(currentX + 1, currentY));
            seen[currentX + 1][currentY] = true;
        }
        if (currentY > 0 && !seen[currentX][currentY - 1] && grid[currentX][currentY - 1] == '1') {
            q.push(pair<int, int>(currentX, currentY - 1));
            seen[currentX][currentY - 1] = true;
        }
        if (currentY < grid[0].size() - 1 && !seen[currentX][currentY + 1] && grid[currentX][currentY + 1] == '1') {
            q.push(pair<int, int>(currentX, currentY + 1));
            seen[currentX][currentY + 1] = true;
        }
    }
}

int numIslands(vector<vector<char>>& grid) {
    int numComponents = 0;
    vector<vector<bool>> seen(grid.size(), vector<bool>(grid[0].size(), false));
    for (int i = 0; i < grid.size(); ++i) {
        for (int j = 0; j < grid[0].size(); ++j) {
            if (!seen[i][j] && grid[i][j] == '1') {
                bfs(seen, grid, i, j);
                ++numComponents;
            }
        }
    }
    return numComponents;
}

Still had a few hiccups - in the last conditional, I originally had currentY < grid.size() - 1 instead of currentY < grid[0].size() - 1 because I was copy-pasting, and I forgot to actually use seen at first…what’s the saying, always be suspicious if your code works immediately the first try? Well, no need to be suspicious I guess.

It turns out you can avoid using a seen matrix, but only if you are allowed to modify grid. Instead of keeping a seen array, overwrite 1 values during BFS with a non-1 value. This doesn’t reduce time complexity, but if you exclude the input grid from the memory analysis then you reduce memory consumption to O(1). Here below, I have overwritten it to 2 to distinguish it from water; you can imagine that after running this function, you could “clean” it by passing over again in \(O(mn)\) time and setting every 2 to 1.

void bfs(vector<vector<char>>& grid, int i, int j) {
    queue<pair<int, int>> q;
    q.push(pair<int, int>(i, j));
    while (!q.empty()) {
        int currentX = q.front().first, currentY = q.front().second;
        q.pop();
        if (currentX > 0 && grid[currentX - 1][currentY] == '1') {
            q.push(pair<int, int>(currentX - 1, currentY));
            grid[currentX - 1][currentY] = '2';
        }
        if (currentX < grid.size() - 1 && grid[currentX + 1][currentY] == '1') {
            q.push(pair<int, int>(currentX + 1, currentY));
            grid[currentX + 1][currentY] = '2';
        }
        if (currentY > 0 && grid[currentX][currentY - 1] == '1') {
            q.push(pair<int, int>(currentX, currentY - 1));
            grid[currentX][currentY - 1] = '2';
        }
        if (currentY < grid[0].size() - 1 && grid[currentX][currentY + 1] == '1') {
            q.push(pair<int, int>(currentX, currentY + 1));
            grid[currentX][currentY + 1] = '2';
        }
    }
}

int numIslands(vector<vector<char>>& grid) {
    int numComponents = 0;
    for (int i = 0; i < grid.size(); ++i) {
        for (int j = 0; j < grid[0].size(); ++j) {
            if (grid[i][j] == '1') {
                bfs(grid, i, j);
                ++numComponents;
            }
        }
    }
    return numComponents;
}