Number of Islands

Introduction

A 2D grid of '1's (land) and '0's (water) arrives, and you have to report how many separate islands it contains — where an island is any maximal blob of 4-connected land cells. The interview version of the problem looks like a puzzle; the actual content is graph theory in costume.

The move: read the grid as an implicit graph. Every cell is a vertex. Every pair of 4-adjacent land cells is an edge. An island is a connected component of the land-cell subgraph. The question collapses to “count connected components,” and you’ve met that problem a hundred times — flood fill, union-find, BFS from each unvisited seed, take your pick.

The grid is not the problem. It’s the graph in disguise. Every flood-fill problem becomes tractable the moment you see it that way.

If you’re early in graph prep, walk through the DFS approach and the viz first. If you already know DFS cold, the two sections worth your time are the BFS “mark on enqueue, not dequeue” subtlety and the union-find treatment — both are where candidates stumble under pressure.

What the interviewer is actually testing

Four signals:

1. Graph recognition. Do you name the grid as an implicit graph in the first thirty seconds? Candidates who don’t spend the rest of the interview reinventing BFS.
2. Component-counting structure. Do you articulate the outer-loop-plus-inner-visit pattern? The outer loop triggers one visit per component; the inner visit is the mechanics.
3. In-place vs auxiliary bookkeeping. Do you notice that the grid itself can double as the visited matrix? This is the micro-optimization that cuts auxiliary space from $O(nm)$ to $O(1)$ (plus recursion/queue).
4. Idiomatic traversal. Does your DFS stop cleanly at boundaries and water cells? Do you know the BFS enqueue-vs-dequeue marking trap? Can you reach for union-find when it genuinely helps (streaming, incremental merging)?

Problem statement

Clarifying questions — and why each one matters

A mental framework — the grid is an implicit graph

When a problem hands you a grid, stop looking at the grid. Look at the graph:

• Vertices: every cell.
• Edges: connect 4-adjacent cells that share a property (both are land).
• Question: usually a property of the graph — connected components, shortest path, spanning tree — dressed in grid language.

Once you see it that way, the move is mechanical. To count connected components in any graph, you do this:

1. Maintain a visited set, initially empty.
2. For every vertex v, if v is not yet visited and satisfies the component condition, increment the counter and run a traversal from v that marks every vertex reachable from v as visited.
3. Return the counter.

For our grid, the “vertices” are cells, “visited” is either a separate matrix or the grid itself (flipping land to water), and “traversal” is DFS or BFS restricted to land cells. Everything else is detail.

Discussion

#include <vector>

class Solution {
  public:
    int numIslands(std::vector<std::vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        const int n = static_cast<int>(grid.size());
        const int m = static_cast<int>(grid[0].size());
        int islands = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == '1') {
                    ++islands;
                    sink(grid, i, j, n, m);
                }
            }
        }
        return islands;
    }

  private:
    void sink(std::vector<std::vector<char>>& grid, int i, int j, int n, int m) {
        if (i < 0 || i >= n || j < 0 || j >= m || grid[i][j] != '1') return;
        grid[i][j] = '0';
        sink(grid, i + 1, j, n, m);
        sink(grid, i - 1, j, n, m);
        sink(grid, i, j + 1, n, m);
        sink(grid, i, j - 1, n, m);
    }
};

#include <array>
#include <queue>
#include <utility>
#include <vector>

class Solution {
  public:
    int numIslands(std::vector<std::vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        const int n = static_cast<int>(grid.size());
        const int m = static_cast<int>(grid[0].size());
        int islands = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == '1') {
                    ++islands;
                    bfs(grid, i, j, n, m);
                }
            }
        }
        return islands;
    }

  private:
    void bfs(std::vector<std::vector<char>>& grid, int si, int sj, int n, int m) {
        static constexpr std::array<std::pair<int, int>, 4> dirs{{
            {-1, 0}, {1, 0}, {0, -1}, {0, 1},
        }};
        std::queue<std::pair<int, int>> q;
        q.emplace(si, sj);
        grid[si][sj] = '0';
        while (!q.empty()) {
            auto [i, j] = q.front();
            q.pop();
            for (const auto& [di, dj] : dirs) {
                const int ni = i + di;
                const int nj = j + dj;
                if (ni >= 0 && ni < n && nj >= 0 && nj < m && grid[ni][nj] == '1') {
                    grid[ni][nj] = '0';
                    q.emplace(ni, nj);
                }
            }
        }
    }
};

#include <numeric>
#include <utility>
#include <vector>

class DSU {
  public:
    explicit DSU(int n) : parent_(n), rank_(n, 0), components_(0) {
        std::iota(parent_.begin(), parent_.end(), 0);
    }

    int find(int x) {
        while (parent_[x] != x) {
            parent_[x] = parent_[parent_[x]];
            x = parent_[x];
        }
        return x;
    }

    void unite(int a, int b) {
        int ra = find(a);
        int rb = find(b);
        if (ra == rb) return;
        if (rank_[ra] < rank_[rb]) std::swap(ra, rb);
        parent_[rb] = ra;
        if (rank_[ra] == rank_[rb]) ++rank_[ra];
        --components_;
    }

    void addSingleton() { ++components_; }
    int components() const { return components_; }

  private:
    std::vector<int> parent_;
    std::vector<int> rank_;
    int components_;
};

class Solution {
  public:
    int numIslands(std::vector<std::vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        const int n = static_cast<int>(grid.size());
        const int m = static_cast<int>(grid[0].size());
        DSU dsu(n * m);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] != '1') continue;
                dsu.addSingleton();
                const int here = i * m + j;
                if (i > 0 && grid[i - 1][j] == '1') dsu.unite(here, (i - 1) * m + j);
                if (j > 0 && grid[i][j - 1] == '1') dsu.unite(here, i * m + (j - 1));
            }
        }
        return dsu.components();
    }
};

Approach comparison

Default answer for the static problem: DFS recursive with in-place marking. State that out loud when you close.

Follow-ups to anticipate

Pattern recognition — flood fill and connected components

The move this problem teaches — grid as implicit graph, outer scan triggers inner traversal per component — is one of the most reused patterns in interviews. Once you see it, half a dozen problems become applications of the same template:

• Flood Fill (LeetCode 733). Paint a color starting from a seed cell. Literally the inner DFS of this problem.
• Max Area of Island (LC 695). Same outer loop; DFS returns a size instead of mutating to count triggers.
• Surrounded Regions (LC 130). Invert the question: flood-fill from the border to mark “safe” cells; flip everything else.
• Walls and Gates (LC 286). Multi-source BFS from every gate; BFS distance replaces DFS reach.
• Pacific Atlantic Water Flow (LC 417). Two independent floods from opposite borders; intersect the results.
• Making A Large Island (LC 827). Label each island with an id and its size; for each water cell, sum the neighboring distinct-id sizes.

The reflex you want: when a problem hands you a 2D grid and asks for “how many blobs” or “reach from here to here” or “fill this color”, the answer is a variant of this template. Start with the graph view; the code falls out in ten lines.

What to say out loud — the delivery script

Ten beats. Rehearse until fluid.

1. “Let me restate: count the number of maximal 4-connected land components in a 2D grid.”
2. Ask: “diagonals not connected, right? Can I mutate the grid? How large does it get?”
3. “I’ll read the grid as an implicit graph. Each cell is a vertex; 4-adjacent land cells share an edge. Counting islands = counting connected components.”
4. “The standard structure is: outer loop over every cell; on each unvisited land cell, fire a DFS to sink the whole component; increment a counter once per trigger.”
5. “I’ll mark cells visited in place by flipping '1' to '0'. That saves an extra visited matrix and collapses ‘already visited’ into ‘now water.’”
6. Write the DFS — four lines. Base case: out of bounds or not land. Mark, then recurse on four neighbors.
7. Write the outer loop — two nested for-loops, counter increments on trigger.
8. “Complexity: $O(nm)$ time, each cell touched a bounded number of times. Space is $O(nm)$ worst-case recursion depth if the grid is one long snake island.”
9. “Two alternatives worth naming: BFS with a queue is the same complexity with bounded queue space — safer on huge grids. Union-find is the right tool if the input is streaming or we need to merge regions.”
10. “Edge cases: empty grid, all water, all land, single row — the recursion’s base case handles them without special cases. I’d ship the DFS version.”

Summary

Number of Islands is a connected-components problem wearing a 2D-grid costume. The algorithm is the textbook one: outer scan finds component heads, inner DFS (or BFS) sinks each component, count the triggers. The real interview signal isn’t the code — it’s articulating the grid-as-graph view, knowing when BFS beats DFS on stack pressure, and spotting when union-find is the right tool (streaming updates, region merging) versus when it’s just showing off.

The pattern generalizes to flood-fill, max-area-of-island, surrounded regions, and most grid problems an interviewer will hand you. Internalize the outer-scan-plus-inner-traversal template here; it will carry you through the rest of the grid-problem family without a single new idea.