aboutsummaryrefslogtreecommitdiff
path: root/pacific_atlantic_water_flow.py
blob: b122610fd53b3ff3283d897c73dd70bda99382bf (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
# 417. Pacific Atlantic Water Flow
from collections import deque

"""
there is an 'm x n' rectangular island that bords both the pacific and
atlantic ocean. the pacific ocean touches the island's left and top edges,
and the atlantic ocean touches the islands right and bottom edges. the island
is partitioned into a grid of square cells. you are given an 'm x n' integer
matrix 'heights' where 'heights[r][c]' represents the height above sea level
of the cell at coordinate '(r, c)'. the island receives a lot of rain, and
the rain water can flow to neighbouring cells directly in any cardinal
direction. return a 2d list of grid coordinates 'result' where 'result[i] =
[r_i, c_i]' denotes that rain water can flow from cell '(r_i, c_i)' to both
the pacific and atlantic oceans.
"""


class Solution(object):
    def pacificAtlantic(self, heights):
        """
        :type heights: List[List[int]]
        :rtype: List[List[int]]
        """
        if not heights or not heights[0]:
            return []
        n, m = len(heights), len(heights[0])

        def bfs(start):
            q = deque(start)
            vis = set(start)
            while q:
                x, y = q.popleft()
                for dx, dy in [(x, y + 1), (x, y - 1), (x - 1, y), (x + 1, y)]:
                    if (
                        0 <= dx < n
                        and 0 <= dy < m
                        and (dx, dy) not in vis
                        and heights[dx][dy] >= heights[x][y]
                    ):
                        q.append((dx, dy))
                        vis.add((dx, dy))
            return vis

        pacific = [(0, i) for i in range(m)] + [(i, 0) for i in range(1, n)]
        atlantic = [(n - 1, i) for i in range(m)] + [(i, m - 1) for i in range(n - 1)]
        return bfs(pacific) & bfs(atlantic)


if __name__ == "__main__":
    obj = Solution()
    print(
        obj.pacificAtlantic(
            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],
            ]
        )
    )
    print(obj.pacificAtlantic(heights=[[1]]))