Pacific Atlantic Water Flow - 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 CURRENT = 'current', CURRENT_COLOR = 'orange';
const NEIGHBOR = 'neighbor', NEIGHBOR_COLOR = 'purple';
const CAN_FLOW = 'can_flow_to_ocean', CAN_FLOW_COLOR = 'lightblue';
const CAN_NOT_FLOW = 'can_not_flow_to_ocean', CAN_NOT_FLOW_COLOR = 'red';
const RESULT = 'result_cell', RESULT_COLOR = 'green';

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

    startBatch();
    const heights = new VisArray2D(...inputHeights.map(row => new VisArray(...row)));
    const rowCount = heights.length;
    const colCount = heights[0].length;
    const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    const result = [];
    const canFlowToPacific = new VisArray2D(...Array.from({ length: rowCount }, () => new VisArray(...Array(colCount).fill(false))));
    const canFlowToAtlantic = new VisArray2D(...Array.from({ length: rowCount }, () => new VisArray(...Array(colCount).fill(false))));
    const queue = new VisQueue().options({ labelExtractionPolicy: JSON.stringify });
    endBatch();

    // Note that the oceanName parameter is not part of the original algorithm introduced just for animation
    const bfs = (canFlowMatrix, oceanName) => {
        while (!queue.isEmpty()) {
            startPartialBatch();
            const [rowIndex, colIndex] = queue.dequeue();
            const currentVM = heights.makeVisManagerForIndexPair(rowIndex, colIndex).addClass(CURRENT);
            notification(`
                🌊 Dequeued cell ${makeColoredSpan(`(${rowIndex}, ${colIndex})`, CURRENT_COLOR)} for ${oceanName} — 
                now visiting its unmarked neighbors to see which ones can flow to the ocean through 
                ${makeColoredSpan('this cell', CURRENT_COLOR)}.
            `);

            for (const [dr, dc] of directions) {
                const neighborRowIndex = rowIndex + dr;
                const neighborColIndex = colIndex + dc;

                if (
                    neighborRowIndex < 0 ||
                    neighborRowIndex >= rowCount ||
                    neighborColIndex < 0 ||
                    neighborColIndex >= colCount ||
                    canFlowMatrix[neighborRowIndex][neighborColIndex]
                ) continue;

                const neighborVM = heights.makeVisManagerForIndexPair(neighborRowIndex, neighborColIndex).addClass(NEIGHBOR);

                if (heights[neighborRowIndex][neighborColIndex] < heights[rowIndex][colIndex]) {
                    neighborVM.addClass(CAN_NOT_FLOW);
                    notification(`
                        🚫 Neighbor ${makeColoredSpan(`(${neighborRowIndex}, ${neighborColIndex})`, NEIGHBOR_COLOR)} 
                        cannot flow the ocean through ${makeColoredSpan('current cell', CURRENT_COLOR)} — 
                        its elevation is lower.
                    `);
                    neighborVM.removeClass(CAN_NOT_FLOW).removeClass(NEIGHBOR);
                    continue;
                }

                canFlowMatrix[neighborRowIndex][neighborColIndex] = true;
                queue.enqueue([neighborRowIndex, neighborColIndex]);
                neighborVM.removeClass(NEIGHBOR).addClass(CAN_FLOW);
                notification(`
                    💧 Neighbor ${makeColoredSpan(`(${neighborRowIndex}, ${neighborColIndex})`, NEIGHBOR_COLOR)} 
                    can flow to ${oceanName} through ${makeColoredSpan('this cell', CURRENT_COLOR)} — 
                    marked and enqueued to explore its own unmarked neighbors that may flow through it later.
                `);
            }

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

    // Note that the oceanName parameter is not part of the original algorithm introduced just for animation
    const initializeFlow = (canFlowMatrix, oceanName, isPacific) => {
        startPartialBatch();
        notification(`
            🌊 Starting ${oceanName} traversal from the ${isPacific ? 'top and left' : 'bottom and right'} edges — 
            these cells can directly flow to ${oceanName} because they lie adjacent to it.
        `);
        startBatch();
        for (let rowIndex = 0; rowIndex < rowCount; rowIndex++) {
            const col = isPacific ? 0 : colCount - 1;
            canFlowMatrix[rowIndex][col] = true;
            queue.enqueue([rowIndex, col]);
            heights.makeVisManagerForIndexPair(rowIndex, col).addClass(CAN_FLOW);
        }
        for (let colIndex = 0; colIndex < colCount; colIndex++) {
            const row = isPacific ? 0 : rowCount - 1;
            if (!canFlowMatrix[row][colIndex]) {
                canFlowMatrix[row][colIndex] = true;
                queue.enqueue([row, colIndex]);
                heights.makeVisManagerForIndexPair(row, colIndex).addClass(CAN_FLOW);
            }
        }
        endBatch();
        endBatch();
    };

    // === Pacific ===
    initializeFlow(canFlowToPacific, 'Pacific', true);
    bfs(canFlowToPacific, 'Pacific');
    clearBoard(heights, canFlowToPacific);

    // === Atlantic ===
    initializeFlow(canFlowToAtlantic, 'Atlantic', false);
    bfs(canFlowToAtlantic, 'Atlantic');
    clearBoard(heights, canFlowToAtlantic);

    // === Final Result ===
    startPartialBatch();
    notification(`🔍 Scanning cells that can flow to both oceans.`);
    for (let rowIndex = 0; rowIndex < rowCount; rowIndex++) {
        for (let colIndex = 0; colIndex < colCount; colIndex++) {
            if (canFlowToPacific[rowIndex][colIndex] && canFlowToAtlantic[rowIndex][colIndex]) {
                result.push([rowIndex, colIndex]);
                heights.makeVisManagerForIndexPair(rowIndex, colIndex).addClass(RESULT);
                notification(`✔️ Cell (${rowIndex}, ${colIndex}) can flow to both Pacific and Atlantic oceans.`);
            }
        }
    }
    endBatch();

    notification(`🏁 <b>Done!</b> Total ${result.length} cells can flow to both oceans.`);
    return result;
}

// --- Visual Setup ---
function initClassProperties() {
    setClassProperties(CURRENT, { borderColor: CURRENT_COLOR });
    setClassProperties(NEIGHBOR, { borderColor: NEIGHBOR_COLOR, backgroundOpacity: 0.5, borderDasharray: '5,5' });
    setClassProperties(CAN_NOT_FLOW, { backgroundColor: CAN_NOT_FLOW_COLOR });
    setClassProperties(CAN_FLOW, { backgroundColor: CAN_FLOW_COLOR });
    setClassProperties(RESULT, { backgroundColor: RESULT_COLOR });
}

function clearBoard(board, marked) {
    startBatch();
    for (let rowIndex = 0; rowIndex < board.length; rowIndex++) {
        for (let colIndex = 0; colIndex < board[rowIndex].length; colIndex++) {
            if (marked[rowIndex][colIndex]) {
                board.makeVisManagerForIndexPair(rowIndex, colIndex).removeAllClasses();
            }
        }
    }
    endBatch();
}

function explanationAndColorSchemaNotifications() {
    explanationNotification();
    notification(`
        🎨 <b>Visual Cues:</b>
        <ul>
            <li>${makeColoredSpan('Current cell', CURRENT_COLOR)} — highlighted with an ${CURRENT_COLOR} border while being dequeued and processed.</li>
            <li>${makeColoredSpan('Neighbor cell', NEIGHBOR_COLOR)} — outlined with a ${NEIGHBOR_COLOR} dashed border when being inspected as a neighbor of the current cell.</li>
            <li>${makeColoredSpan('Neighbor too low to flow', CAN_NOT_FLOW_COLOR)} — shaded ${CAN_NOT_FLOW_COLOR} when its elevation is lower than the current cell, so it cannot flow toward the ocean through the current cell.</li>
            <li>${makeColoredSpan('Neighbor marked as can flow', CAN_FLOW_COLOR)} — filled with ${CAN_FLOW_COLOR} background once it’s marked and enqueued as able to flow to the current ocean.</li>
            <li>${makeColoredSpan('Result cell', RESULT_COLOR)} — filled with ${RESULT_COLOR} background when it can flow to <b>both</b> oceans.</li>
        </ul>
    `);
}

Approach

We start from what we already know: cells on an ocean's border can clearly flow into that ocean (they are directly adjacent to it).
For each ocean, we:
- Mark its border cells as able to flow to that ocean,
- Push them into a queue as our initial "known-good" sources.
While traversing, we maintain:
- a queue — containing the cells already known to reach the ocean but not yet dequeued, meaning their unmarked neighbors have not been checked against them;
- a marked (boolean) matrix — canFlowMatrix, indicating which cells are already known to be able to flow to this ocean;
From there, we repeatedly expand inward using BFS: when we take a cell (r, c) from the queue (a cell that is already confirmed to reach this ocean), we inspect its 4 neighbors (nr, nc).
A neighbor (nr, nc) is also marked as able to reach this ocean and added to the queue if:
- it is inside the grid,
- it has not been marked yet for this ocean, and
- heights[nr][nc] ≥ heights[r][c].
This condition encodes the key idea: if water can flow from (nr, nc) down to (r, c), and (r, c) is already known to reach the ocean, then (nr, nc) can also reach that ocean through (r, c).
In other words, we are growing the set of cells that are proven to reach the ocean: we start from confirmed ocean-adjacent cells and, via BFS, keep adding neighbors that can flow into any confirmed cell. The queue always holds cells that are already known to reach the ocean but have not yet been dequeued, so their unmarked neighbors (where canFlowMatrix[neighborRowIndex][neighborColIndex] is not yet true) have not been checked against them. Whenever we just discover that a neighbor can flow to the ocean, we mark it and enqueue it.
We run this process separately for:
- Pacific: starting from top row and left column,
- Atlantic: starting from bottom row and right column.
This yields two boolean grids: canFlowToPacific and canFlowToAtlantic.
Finally, we scan all cells and collect those where canFlowToPacific[r][c] and canFlowToAtlantic[r][c] are both true. These are exactly the cells that can flow to both oceans.

Time Complexity

O(m × n)

Let m be the number of rows and n be the number of columns in the grid.
Each cell can be enqueued and processed at most once for the Pacific BFS and at most once for the Atlantic BFS.
For each processed cell, we check up to 4 neighbors in O(1) time.
Therefore, the total work across both traversals is linear in the number of cells: O(m × n).

Space Complexity

O(m × n)

m is the number of rows and n is the number of columns in the grid.
We maintain two boolean matrices, canFlowToPacific and canFlowToAtlantic, each of size m × n.
The BFS queue holds the cells already known to reach the ocean but not yet dequeued, and its size is maximized during the initialization phase when it contains all edge cells — O(m + n).
Other auxiliary data structures use constant space.
Hence, the total auxiliary space is O(m × n).

Input-1

Pacific Atlantic Water Flow - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

Time Complexity

Space Complexity