Description
Return cells from which water can reach both the top/left ocean and bottom/right ocean, moving only to equal or lower adjacent heights.
Solution
def pacific_atlantic(heights):
rows, cols = len(heights), len(heights[0])
def reach(starts):
seen = set(starts)
stack = list(seen)
while stack:
r,c = stack.pop()
for dr,dc in ((1,0),(-1,0),(0,1),(0,-1)):
x,y = r+dr,c+dc
if 0 <= x < rows and 0 <= y < cols and (x,y) not in seen and heights[x][y] >= heights[r][c]:
seen.add((x,y))
stack.append((x,y))
return seen
pac = reach([(0,c) for c in range(cols)]+[(r,0) for r in range(rows)])
atl = reach([(rows-1,c) for c in range(cols)]+[(r,cols-1) for r in range(rows)])
return [list(p) for p in sorted(pac & atl)]Examples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[[1]]]- Output
[[0,0]]
The only cell touches both oceans.
Example 2
- Input
[[[1,1],[1,1]]]- Output
[[0,0],[0,1],[1,0],[1,1]]
Equal heights allow flow throughout the board.
Example 3
- Input
[[[1,2],[3,4]]]- Output
[[0,1],[1,0],[1,1]]
Every cell except the top-left can reach both borders.
Approach
Traverse uphill in reverse from each ocean's border and intersect reachable sets.
Time & space
O(R C) time; O(R C) auxiliary space for R rows and C columns, excluding the result.