aboutsummaryrefslogtreecommitdiff
path: root/pacific_atlantic_water_flow.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-10-04 19:37:59 -0600
committerJack Sangdahl <[email protected]>2025-10-04 19:37:59 -0600
commitb655133617e644bd958c4b3356c04ad7a92718f1 (patch)
tree2ef7ec928f100479309585d29777630a28925352 /pacific_atlantic_water_flow.py
parentbadbb55eba0ccf863d56ded03317f945f250850a (diff)
downloadleetcode-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.py62
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]]))