Pacific Atlantic Water Flow
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]]
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;}