There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges. The island is partitioned int

pacificAtlantic.js

/**
 * Given a matrix of heights, returns coordinates of cells that can flow to both the Pacific and Atlantic oceans.
 * Pacific touches the left and top edges; Atlantic touches the right and bottom edges.
 * @param {number[][]} heights - 2D grid of elevation values
 * @return {number[][]} - List of coordinates [i, j] that can reach both oceans
 */
var pacificAtlantic = function(heights) {
    let row = heights.length;
    let col = heights[0].length;
    let arr = []; // Stores final result: cells that can reach both oceans
    let obj = {}; // Memoization object to avoid redundant checks

    // Iterate through every cell in the matrix
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            var atlantic = false; var pacific = false;

            // Recursively check if water from cell (i, j) can reach both oceans
            out(i, j, heights);

            // If both flags are true, add cell to result and memoize it
            if (pacific && atlantic) {
                arr.push([i, j]);
                obj[i + ' ' + j] = 1;
            }
        }
    }

    return arr;

    function out(i, j, heights) {
        // If already memoized, mark both oceans as reachable and return
        if (obj[i + ' ' + j]) {
            pacific = true;
            atlantic = true;
            return;
        }

        // Check if cell touches Pacific (top or left edge)
        if (j === 0 || i === 0) pacific = true;

        // Check if cell touches Atlantic (bottom or right edge)
        if (j === col - 1 || i === row - 1) atlantic = true;

        // If both oceans are already reachable, stop recursion
        if (pacific && atlantic) return;

        // Temporarily mark cell as visited to avoid cycles
        let value = heights[i][j];
        heights[i][j] = Infinity;

        // Explore neighboring cells if water can flow downhill or level
        if (i < row - 1 && value >= heights[i + 1][j]) out(i + 1, j, heights);
        if (i > 0 && value >= heights[i - 1][j]) out(i - 1, j, heights);
        if (j < col - 1 && value >= heights[i][j + 1]) out(i, j + 1, heights);
        if (j > 0 && value >= heights[i][j - 1]) out(i, j - 1, heights);

        // Restore original height after recursion
        heights[i][j] = value;
    }
};