diff options
author | Jack Sangdahl <[email protected]> | 2025-10-04 19:37:59 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-10-04 19:37:59 -0600 |
commit | b655133617e644bd958c4b3356c04ad7a92718f1 (patch) | |
tree | 2ef7ec928f100479309585d29777630a28925352 /pacific_atlantic_water_flow.py | |
parent | badbb55eba0ccf863d56ded03317f945f250850a (diff) | |
download | leetcode-b655133617e644bd958c4b3356c04ad7a92718f1.tar.gz leetcode-b655133617e644bd958c4b3356c04ad7a92718f1.zip |
417. pacific atlantic water flow
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]])) |