Number of Islands - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const VISITED = 'visited', VISITED_COLOR = 'gold';
const IN_QUEUE = 'in_queue', IN_QUEUE_COLOR = 'lightblue';
const CURRENT = 'current', CURRENT_COLOR = 'orange';
const ISLAND_START = 'island_start', ISLAND_START_COLOR = 'green';

function visMainFunction(gridInput) {
    initClassProperties();
    explanationAndColorSchemaNotifications();

    startBatch();
    const grid = new VisArray2D(...gridInput.map(row => new VisArray(...row)));
    const rowCount = grid.length;
    const colCount = grid[0].length;
    const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];

    let islandCount = 0;
    makeVisVariable(islandCount).options({ label: 'islandCount' }).createVis();
    endBatch();

    const bfs = (startRow, startCol) => {
        startPartialBatch();

        notification(`
            📥 Starting BFS from the cell at (${startRow}, ${startCol}) — this cell is the starting point of this island.
            We immediately mark it as visited in-place (set to '0') and enqueue it.
            The BFS queue is initialized with this starting cell and, throughout the search, it will hold land cells already
            confirmed to be part of this island but not yet dequeued to explore their unvisited neighboring land cells.
            We dequeue them one by one to expand through all connected '1's.
        `);
        const queue = new VisQueue([[startRow, startCol]]).options({ label: 'BFS Queue', labelExtractionPolicy: JSON.stringify });
        grid[startRow][startCol] = '0';
        grid.makeVisManagerForIndexPair(startRow, startCol).removeClass(ISLAND_START).addClass(IN_QUEUE);

        endBatch();

        while (!queue.isEmpty()) {
            startPartialBatch();

            const [row, col] = queue.dequeue();
            const currentVM = grid.makeVisManagerForIndexPair(row, col)
                .removeClass(IN_QUEUE)
                .addClass(CURRENT);

            notification(`
                🔎 Dequeued ${makeColoredSpan(`cell at (${row}, ${col})`, CURRENT_COLOR)} — exploring its 4-directional neighbors to expand the current island.
                Whenever we find a neighboring land cell ('1'), we mark it as visited <b>in-place</b> by setting it to '0' — this prevents reprocessing the same cell
                and saves extra space by avoiding a separate visited matrix. We then enqueue it so its own unvisited land neighbors can be explored in subsequent BFS steps.
            `);

            for (const [dr, dc] of directions) {
                const neighborRow = row + dr;
                const neighborCol = col + dc;

                if (
                    neighborRow >= 0 && neighborRow < rowCount &&
                    neighborCol >= 0 && neighborCol < colCount &&
                    grid[neighborRow][neighborCol] === '1'
                ) {
                    grid[neighborRow][neighborCol] = '0';
                    queue.enqueue([neighborRow, neighborCol]);
                    grid.makeVisManagerForIndexPair(neighborRow, neighborCol).addClass(IN_QUEUE);
                }
            }

            currentVM.removeClass(CURRENT).addClass(VISITED);
            endBatch();
        }
    };

    for (let row = 0; row < rowCount; row++) {
        for (let col = 0; col < colCount; col++) {
            if (grid[row][col] === '1') {
                startPartialBatch();
                grid.makeVisManagerForIndexPair(row, col).addClass(ISLAND_START);
                notification(`
                    🟩 Found new unvisited land at (${row}, ${col}) — this marks the beginning of a new island.
                    Incrementing <code>islandCount</code> and launching BFS to explore all connected land cells ('1'),
                    marking them as visited in-place (set to '0') so they won’t be counted again.
                `);
                islandCount += 1;
                endBatch();
                bfs(row, col);
            }
        }
    }

    notification(`🏁 <b>Done!</b> Total number of distinct islands: <b>${islandCount}</b>.`);
    return islandCount;
}

function initClassProperties() {
    setClassProperties(VISITED, { backgroundColor: VISITED_COLOR });
    setClassProperties(IN_QUEUE, { backgroundColor: IN_QUEUE_COLOR });
    setClassProperties(CURRENT, { borderColor: CURRENT_COLOR });
    setClassProperties(ISLAND_START, { backgroundColor: ISLAND_START_COLOR });
}

function explanationAndColorSchemaNotifications() {
    explanationNotification();

    notification(`
        🎨 <b>Visual cues:</b>
        <ul>
            <li>
            ${makeColoredSpan('Island start cell', ISLAND_START_COLOR)} — ${ISLAND_START_COLOR} background;
            a newly discovered land cell <code>'1'</code> that starts a new island and triggers BFS.
            </li>
            <li>
            ${makeColoredSpan('In queue', IN_QUEUE_COLOR)} — ${IN_QUEUE_COLOR} background;
            land cells that are marked visited (set to <code>'0'</code>) and enqueued,
            waiting for their unvisited neighboring lands to be explored.
            </li>
            <li>
            ${makeColoredSpan('Current cell', CURRENT_COLOR)} — ${CURRENT_COLOR} border;
            the cell just dequeued from the BFS queue to explore its unvisited neighboring lands.
            </li>
            <li>
            ${makeColoredSpan('Visited cell', VISITED_COLOR)} — ${VISITED_COLOR} background;
            a cell whose neighboring lands have been fully explored.
            </li>
        </ul>
    `);
}

Approach

We are given an m × n grid where:
- '1' represents land
- '0' represents water
Two land cells belong to the same island if they are connected horizontally or vertically (4-directionally).
We scan every cell in the grid:
- When we encounter water or already explored land ('0'), we skip it.
- When we encounter unvisited land '1', this cell marks the beginning of a new island. We increment islandCount and launch a BFS to explore all connected land cells ('1'), marking them as visited in-place (set to '0') so they won’t be counted again.
For each new island, we run a BFS:
- The BFS queue is initialized with this starting cell and, throughout the search, it will hold land cells already confirmed to be part of this island but not yet dequeued to explore their unvisited neighboring land cells.
- As soon as we add a land cell to the queue, we mark it as visited in-place by setting its value to '0'. This:
  - prevents reprocessing the same cell, and
  - removes the need for a separate visited matrix.
- While the queue is not empty, we:
  - dequeue a cell (r, c),
  - look at its 4-directional neighbors (nr, nc),
  - for each neighbor that is inside the grid and has value '1', we:
    - mark it visited in-place by setting it to '0',
    - enqueue it to explore its own unvisited land neighbors in subsequent BFS steps.
  This BFS step ensures that all land cells connected to the starting cell are discovered and marked as part of the same island.
Once the BFS from a starting cell finishes, all cells in that island have been visited (set to '0'), so they will not start or belong to any other island. The outer scan then continues to look for the next unvisited land cell to start another island.

Time Complexity

Let m be the number of rows and n be the number of columns in the grid. We scan every cell once, and each land cell ('1') is visited, marked, and processed exactly once during BFS. Each cell may check up to four neighbors, but these operations take constant time overall. Hence, the total work done across all BFS traversals is proportional to the total number of cells, giving a time complexity of O(m × n).

Space Complexity

Let m be the number of rows and n be the number of columns in the grid. The space complexity of this algorithm is O(min(m, n)). The worst case occurs when the grid is entirely filled with land cells, where the BFS queue can grow proportional to min(m, n) cells at its maximum.

Input-1

Number of Islands - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

Time Complexity

Space Complexity