Number of Islands

MediumGraphs

Count the number of islands in a grid of '1' (land) and '0' (water), where islands connect horizontally or vertically.

Constraints

1 <= m, n <= 300
grid[i][j] is '0' or '1'

Flood fill each unvisited land cell

Time O(m * n)Space O(m * n) worst-case recursion

Scan the grid. On each unvisited land cell, increment the count and run DFS/BFS that sinks the whole connected island by marking visited cells, so it is counted once.

#include <bits/stdc++.h>
using namespace std;

int numIslands(vector<vector<char>>& grid) {
    int m = grid.size(), n = grid[0].size(), count = 0;
    function<void(int,int)> sink = [&](int r, int c) {
        if (r < 0 || c < 0 || r >= m || c >= n || grid[r][c] != '1') return;
        grid[r][c] = '0';
        sink(r+1,c); sink(r-1,c); sink(r,c+1); sink(r,c-1);
    };
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (grid[i][j] == '1') { count++; sink(i, j); }
    return count;
}