Pacific Atlantic Water Flow

The problem

Implement `pacificAtlantic(heights)` for an `m x n` grid of heights representing an island bordered by the Pacific (top and left edges) and the Atlantic (bottom and right edges). Water flows from a cell to any of its four neighbours only when the neighbour's height is less than or equal to the current cell's. Return every cell from which water can reach both oceans.

Checking each cell by walking its downhill paths forward would mean re-tracing enormous overlap from up to `R * C` different starting points — the cheaper direction is backwards: BFS out from each ocean's own border, following any edge that's uphill or flat, since that's exactly the reverse of a valid downhill flow into that ocean.

The approach

Reversing the direction is the only real departure from a standard grid BFS: `bfsFromBorder` seeds its queue with an entire ocean's border cells at once — the same multi-source pattern as every other grid BFS in this log — and only enqueues a neighbour when `heights[nr][nc] >= heights[r][c]`, i.e. a cell water could have flowed down *from* to reach here, so walking that edge backwards from the ocean traces every cell whose downhill flow reaches it.

Two independent visited sets come out of two separate `bfsFromBorder` calls — one for cells that reach the Pacific, one for the Atlantic — and a cell only belongs in the answer if it's in *both*, so the last pass is a plain Set-intersection filter over every grid cell rather than a third traversal.

The queue swaps `Array.shift()` for a `head` index that only ever advances. Every earlier BFS in this log popped the front with `.shift()` — an O(n) re-index on every call — while walking the same array with a pointer instead makes each dequeue O(1), which starts to matter once the border seed lists (and therefore the queue) get long.

The solution

class Solution {
    /**
     * @param {number[][]} heights
     * @return {number[][]}
     */
    pacificAtlantic(heights) {
      const rows = heights.length;
      const cols = heights[0].length;
      const key = (r, c) => r * cols + c;

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

      const bfsFromBorder = (starts) => {
        const visited = new Set(starts.map(([r, c]) => key(r, c)));
        const queue = starts.slice();
        let head = 0; // index pointer instead of Array.shift() — O(1) dequeue

        while (head < queue.length) {
          const [r, c] = queue[head++];
          for (const [dr, dc] of DIRECTIONS) {
            const nr = r + dr;
            const nc = c + dc;
            const nk = key(nr, nc);
            if (
              nr >= 0 && nr < rows &&
              nc >= 0 && nc < cols &&
              !visited.has(nk) &&
              heights[nr][nc] >= heights[r][c]
            ) {
              visited.add(nk);
              queue.push([nr, nc]);
            }
          }
        }
        return visited;
      };

      const pacificStarts = [];
      const atlanticStarts = [];

      for (let r = 0; r < rows; r++) {
        pacificStarts.push([r, 0]);
        atlanticStarts.push([r, cols - 1]);
      }

      for (let c = 0; c < cols; c++) {
        pacificStarts.push([0, c]);
        atlanticStarts.push([rows - 1, c]);
      }

      const pacific = bfsFromBorder(pacificStarts);
      const atlantic = bfsFromBorder(atlanticStarts);

      const result = [];

      for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
          const k = key(r, c);
          if (pacific.has(k) && atlantic.has(k)){
            result.push([r, c]);
          }
        }
      }
      return result;
    }
  }

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