Subhra Jyoti Baroieditorial
Chat with me
← Daily Logs
Algorithms

Minimum Island (Grid Flood Fill)

MediumJul 6, 2026gridbfsflood-fillconnected-components

Same island scan as `islandCount`, but track size the way `largestComponent` does and reduce with `Math.min` instead of `Math.max`. The only real wrinkle is picking an identity value that plays nice with a minimum: `Infinity`, not `0` — a real island's size can never lose to it, and 'no island found' is the one case that should come back out as `Infinity` too.

The problem

Implement `minimumIsland(graph)` over the same `'W'`/`'L'` grid as `islandCount`, but return the size of the *smallest* land mass instead of how many exist. Land is still connected up/down/left/right, not diagonally.

If the grid has no land at all, the answer is `Infinity` — there's no smallest island to report, and a fallback like `0` would read as a real (if tiny) answer instead of 'there wasn't one'.

The approach

`exploreGraph` keeps the exact same three rejection cases as `islandCount` — out of bounds, water, already visited — but now returns `Infinity` for all of them instead of `false`. A real island still gets BFS'd and returns its actual size, counted the same way `largestComponent` counted a component: a running `size` incremented each time a new cell is marked visited and queued.

The outer loop does `Math.min(minIslandLength, exploreGraph(...))` across every `(r, c)` in the grid, water and revisited land included. Since `Infinity` can never win a `Math.min` against a real number, only genuine islands ever move the answer — the same trick `largestComponent` used with `0` and `Math.max`, just flipped for the opposite reduction.

That symmetry is also what makes the all-water grid correct for free: every single cell returns `Infinity` from `exploreGraph`, so `minIslandLength` never leaves its initial value and the function returns `Infinity` — exactly the sentinel the empty case needs, with no separate check required.

The solution

js
export function minimumIsland(graph) {
    const visited = new Set();
    let minIslandLength = Infinity;

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

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 Infinity;
    }

    const q = [[r, c]];
    visited.add(pos);
    let size = 1
    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]);
                size++
            }
        }
    }
    return size;
}

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

All entries