Subhra Jyoti Baroieditorial
Chat with me
← Daily Logs
Algorithms

Island Count (Grid Flood Fill)

EasyJul 5, 2026gridbfsflood-fillconnected-components

Connected-components counting, but the graph is a 2D grid instead of an adjacency list — neighbours come from four hardcoded directions instead of a precomputed list, and a node's identity has to be built (`"r,c"`) instead of already being a string key. Everything downstream — shared `visited`, a component-start returning truthy, a running count — is the exact same shape as `connectedComponentsCount`.

The problem

Implement `islandCount(grid)` over a 2D grid of `'W'` (water) and `'L'` (land) cells. Count how many separate land masses exist, where a land mass is a group of `'L'` cells connected up/down/left/right (not diagonally).

There's no adjacency list here — the grid itself is the graph, and a cell's neighbours have to be computed from its coordinates rather than looked up. `islandCount` also has to try every `(r, c)` in the grid as a potential start, including water cells, and rely on `exploreGraph` to reject the ones that don't lead anywhere new.

The approach

`exploreGraph(graph, r, c, visited)` first does the rejection: out-of-bounds, water (`'W'`), or already-visited all return `false` immediately, before anything is queued. That single guard is doing the job `visited.has(source)` alone did in the adjacency-list versions, plus two new reasons a 'node' isn't worth exploring.

A cell's identity is a string, `` `${r},${c}` ``, built solely so `visited` — a `Set` — can dedupe by value. `visited.has([r, c])` would never match a previous `[r, c]` array (different reference every time), so the coordinate pair has to be flattened into a primitive before it can be tracked at all.

The traversal is BFS with a queue of `[r, c]` pairs and a `directions` array of the four unit offsets, but the *shape* is identical to every earlier flood-fill: seed the queue with the start, mark it visited immediately, and for each popped cell check its (computed, not looked-up) neighbours, pushing and marking the unvisited, in-bounds, land ones. `islandCount` itself is just `connectedComponentsCount`'s outer loop with a nested loop for rows/columns instead of `for...in`, and `count++` instead of `+= exploreGraph(...)` since here `exploreGraph` returns a boolean rather than a size.

The solution

js
export function islandCount(graph) {
    const visited = new Set();
    let count = 0;

    for (let r = 0; r < graph.length; r++) {
        for (let c = 0; c < graph[0].length; c++) {
            if (exploreGraph(graph, r, c, visited)) {
                count++;
            }
        }
    }
    return count;
}

export function exploreGraph(graph, r, c, visited) {
    const rowInBound = r >= 0 && r < graph.length;
    const colInBound = c >= 0 && c < graph[0].length;
    const pos = `${r},${c}`;

    if (!rowInBound || !colInBound || graph[r][c] === 'W' || visited.has(pos)) {
        return false;
    }

    const q = [[r, c]];
    visited.add(pos);

    const directions = [
        [1, 0], [-1, 0], [0, 1], [0, -1]
    ];

    while (q.length > 0) {
        const [cr, cc] = q.shift();
        for (const [dr, dc] of directions) {
            const [nr, nc] = [cr + dr, cc + dc];
            const inBounds = nr >= 0 && nr < graph.length && nc >= 0 && nc < graph[0].length;
            const neighborPos = `${nr},${nc}`;
            if (
                inBounds &&
                graph[nr][nc] === 'L' &&
                !visited.has(neighborPos)
            ) {
                visited.add(neighborPos);
                q.push([nr, nc]);
            }
        }
    }
    return true;
}

Time O(R * C)Space O(R * C)

All entries