#417

Pacific Atlantic Water Flow

medium· Graphsruns: 0

There is an m x n rectangular island that borders both the Pacific Ocean (top and left edges) and the Atlantic Ocean (bottom and right edges). The island is partitioned into a grid where heights[r][c] gives the height of cell (r, c). Water flows from a cell to a 4-directionally adjacent cell with height less than or equal to the current cell. Return a list of grid coordinates where water can flow to both oceans.

wpm 0acc 100%time 0:000 / 995

class Solution:
    def pacificAtlantic(
        self, heights: list[list[int]]
    ) -> list[list[int]]:
        rows, cols = len(heights), len(heights[0])
        pacific = set()
        atlantic = set()

        def dfs(r: int, c: int, visited: set, prev: int) -> None:
            if (
                (r, c) in visited
                or r < 0
                or r >= rows
                or c < 0
                or c >= cols
                or heights[r][c] < prev
            ):
                return
            visited.add((r, c))
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                dfs(r + dr, c + dc, visited, heights[r][c])

        for c in range(cols):
            dfs(0, c, pacific, heights[0][c])
            dfs(rows - 1, c, atlantic, heights[rows - 1][c])
        for r in range(rows):
            dfs(r, 0, pacific, heights[r][0])
            dfs(r, cols - 1, atlantic, heights[r][cols - 1])

        return [[r, c] for r, c in pacific & atlantic]

click the box to focus · tab inserts 4 spaces · backspace to correct · esc to pause

desktop only

codedrill is a typing game and needs a real keyboard. open this on a laptop or desktop to practice.

you can still browse problems and sections from your phone.