Number of Islands

Problem

Given a 2D grid grid where '1' represents land and '0' represents water, count and return the number of islands.

An island is formed by connecting adjacent lands horizontally or vertically and is surrounded by water. You may assume water is surrounding the grid (i.e., all the edges are water).

Examples

Example 1:

Input: grid = [
    ["0","1","1","1","0"],
    ["0","1","0","1","0"],
    ["1","1","0","0","0"],
    ["0","0","0","0","0"]
  ]
Output: 1

Example 2:

Input: grid = [
    ["1","1","0","0","1"],
    ["1","1","0","0","1"],
    ["0","0","1","0","0"],
    ["0","0","0","1","1"]
  ]
Output: 4

Constraints

• 1 <= grid.length, grid[i].length <= 100
• grid[i][j] is '0' or '1'.

You should aim for a solution with O(m * n) time and O(m * n) space, where m is the number of rows and n is the number of columns in the grid.

Solution

Perform flood fill over each land tile. As we perform flood fill, we convert to water so we don’t double count.

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int ROWS = grid.size();
        int COLS = grid[0].size();
        int num_islands = 0;
 
        std::function<void(int, int)> dfs;
        dfs = [&](int r, int c) {
            // Out of bounds
            if (r < 0 || c < 0 || r >= ROWS || c >= COLS) {
                return;
            }
            // Not land
            if (grid[r][c] == '0') { return; }
            // Mark as touched, and flood fill
            grid[r][c] = '0';
            dfs(r + 1, c);
            dfs(r - 1, c);
            dfs(r, c + 1);
            dfs(r, c - 1);
        };
 
        // For each cell, if land then perform DFS
        // DFS will perform floodfill and remove land
        //   so we don't double count
        for (int i = 0; i < ROWS; ++i) {
            for (int j = 0; j < COLS; ++j) {
                if (grid[i][j] == '1') {
                    ++num_islands;
                    dfs(i, j);
                }
            }
        }
        return num_islands;
    }
};