Pacific Atlantic Water Flow

Medium

Problem

heights is an island grid. The Pacific touches the top and left edges; the Atlantic touches the bottom and right edges. Water flows from a cell to a neighbour of equal or lower height. Return every cell from which water can reach both oceans.

Example 1

Input:  [[1,2,2,3,5], [3,2,3,4,4], [2,4,5,3,1], [6,7,1,4,5], [5,1,1,2,4]]
Output: [[0,4], [1,3], [1,4], [2,2], [3,0], [3,1], [4,0]]

Test cases

Case 1

Input:    [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Expected (any order): [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

Case 2

Input:    [[1]]
Expected (any order): [[0,0]]

Case 3

Input:    [[1,1],[1,1]]
Expected (any order): [[0,0],[0,1],[1,0],[1,1]]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Reverse flow from each ocean

Time O(R·C)Space O(R·C)

Instead of testing every cell, spread uphill from each ocean’s border. Cells reached from both oceans are the answer.

function pacificAtlantic(h) {
const R = h.length, C = h[0].length;
const mk = () => Array.from({ length: R }, () => new Array(C).fill(false));
const pac = mk(), atl = mk();
const dfs = (r, c, seen) => {
seen[r][c] = true;
for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nc >= 0 && nr < R && nc < C && !seen[nr][nc] && h[nr][nc] >= h[r][c])
dfs(nr, nc, seen);
}
};
for (let r = 0; r < R; r++) { dfs(r, 0, pac); dfs(r, C - 1, atl); }
for (let c = 0; c < C; c++) { dfs(0, c, pac); dfs(R - 1, c, atl); }
const res = [];
for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) if (pac[r][c] && atl[r][c]) res.push([r, c]);
return res;
}