Medium

Pacific Atlantic Water Flow

LAB

Given heights, return coordinates that can flow to both the top/left ocean and the bottom/right ocean, sorted row-major.

EXAMPLES

Example 1

Input
{
  "heights": [
    [
      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
  ]
]

FUNCTION SHAPE

heights: intMatrix→intMatrix

SOLUTION NOTE

This is an interesting problem. This is kinda similar to trapping rain water 2. The idea is we reverse the problem, instead of dfs from the land, we dfs from the water. We 'hill climb', trying to ascend up from the oceans and marking those hills as land which will flow down to the ocean. If we are ever lower than the previous height, we terminate, as water will collect in this valley and not reach the ocean. Any land cell that is both visited from the pacific and atlantic oceans are feasible.

Reveal reference solution +

pythonREFERENCE

def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
    if not heights or not heights[0]:
        return []

    m, n = len(heights), len(heights[0])
    pacific = [[False] * n for _ in range(m)]
    atlantic = [[False] * n for _ in range(m)]

    def dfs(r, c, visited, prevHeight):
        if (r < 0 or r >= m or c < 0 or c >= n or
            visited[r][c] or heights[r][c] < prevHeight):
            return
        visited[r][c] = True
        for dr, dc in [(0,1), (0,-1), (1,0), (-1,0)]:
            dfs(r+dr, c+dc, visited, heights[r][c])

    for i in range(m):
        dfs(i, 0, pacific, heights[i][0])
        dfs(i, n-1, atlantic, heights[i][n-1])
    for j in range(n):
        dfs(0, j, pacific, heights[0][j])
        dfs(m-1, j, atlantic, heights[m-1][j])

    res = []
    for i in range(m):
        for j in range(n):
            if pacific[i][j] and atlantic[i][j]:
                res.append([i, j])
    return res

TimeO(m*n)

SpaceO(m*n)

Open on LeetCode ↗