diff options
Diffstat (limited to 'pacific_atlantic_water_flow.py')
-rw-r--r-- | pacific_atlantic_water_flow.py | 62 |
1 files changed, 62 insertions, 0 deletions
diff --git a/pacific_atlantic_water_flow.py b/pacific_atlantic_water_flow.py new file mode 100644 index 0000000..b122610 --- /dev/null +++ b/pacific_atlantic_water_flow.py @@ -0,0 +1,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]])) |