417. Pacific Atlantic Water Flow

1function pacificAtlantic(heights: number[][]): number[][] {
2  const m = heights.length, n = heights[0].length;
3  const bfs = (seeds: number[][]) => {
4    const ocean = heights.map((row) => row.map(() => false));
5    for (const [r, c] of seeds) ocean[r][c] = true;
6    const queue = [...seeds];
7    while (queue.length) {
8      const [r, c] = queue.shift()!;
9      for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
10        const x = r + dr, y = c + dc;
11        if (x < 0 || y < 0 || x >= m || y >= n || ocean[x][y]) continue;
12        if (heights[x][y] >= heights[r][c]) { ocean[x][y] = true; queue.push([x, y]); }
13      }
14    }
15    return ocean;
16  };
17  const cols = [...Array(n).keys()], rows = [...Array(m).keys()];
18  const pac = bfs([...cols.map((c) => [0, c]), ...rows.map((r) => [r, 0])]);
19  const atl = bfs([...cols.map((c) => [m - 1, c]), ...rows.map((r) => [r, n - 1])]);
20  const res: number[][] = [];
21  for (let r = 0; r < m; r++)
22    for (let c = 0; c < n; c++) if (pac[r][c] && atl[r][c]) res.push([r, c]);
23  return res;
24}

Start from every Pacific border cell and climb to equal-or-higher neighbors.

Space: play/pause · ←/→: step