pacific_atlantic_water_flow
1from collections import deque 2 3 4# @leet start 5class Solution: 6 def pacificAtlantic(self, matrix: list[list[int]]) -> list[list[int]]: 7 """ 8 This question asks us to find the tiles which can reach both the pacific 9 and atlantic ocean, where the pacific is the left and top edge and 10 the atlantic is the bottom and right edge. Water flows from tiles if it has 11 at least the same height or is greater. 12 13 To do this, we can first create two queues, one for the pacific and atlantic 14 oceans, and then add in the reachable edges for both. 15 16 Next, we BFS from both queues. We first create a set that holds the reachable 17 items, and then for each queue, we check to see if we can reach any new nodes 18 by checking its neighbors and making sure its inbounds, reachable, and 19 the the new value is smaller than our current x and y coordinates. 20 If this is correct, we append it to the queue. 21 22 We do this BFS for both the pacific and atlantic oceans and then do 23 set intersection on them to return the set where both oceans 24 are reachable. 25 """ 26 m, n = len(matrix), len(matrix[0]) 27 28 if not matrix or not matrix[0]: 29 return [] 30 31 pacific = deque() 32 atlantic = deque() 33 34 for i in range(m): 35 pacific.append((i, 0)) 36 atlantic.append((i, n - 1)) 37 for i in range(n): 38 pacific.append((0, i)) 39 atlantic.append((m - 1, i)) 40 41 def inbounds(y, x): 42 return 0 <= y < m and 0 <= x < n 43 44 def bfs(q): 45 reachable = set() 46 while q: 47 y, x = q.popleft() 48 reachable.add((y, x)) 49 for dy, dx in [(0, 1), (1, 0), (-1, 0), (0, -1)]: 50 new_y, new_x = dy + y, dx + x 51 if not inbounds(new_y, new_x): 52 continue 53 if (new_y, new_x) in reachable: 54 continue 55 if matrix[new_y][new_x] < matrix[y][x]: 56 continue 57 q.append((new_y, new_x)) 58 return reachable 59 60 return list(bfs(pacific) & bfs(atlantic)) 61 62 63# @leet end 64 65 66def test(): 67 assert 2 + 2 == 4
class
Solution:
6class Solution: 7 def pacificAtlantic(self, matrix: list[list[int]]) -> list[list[int]]: 8 """ 9 This question asks us to find the tiles which can reach both the pacific 10 and atlantic ocean, where the pacific is the left and top edge and 11 the atlantic is the bottom and right edge. Water flows from tiles if it has 12 at least the same height or is greater. 13 14 To do this, we can first create two queues, one for the pacific and atlantic 15 oceans, and then add in the reachable edges for both. 16 17 Next, we BFS from both queues. We first create a set that holds the reachable 18 items, and then for each queue, we check to see if we can reach any new nodes 19 by checking its neighbors and making sure its inbounds, reachable, and 20 the the new value is smaller than our current x and y coordinates. 21 If this is correct, we append it to the queue. 22 23 We do this BFS for both the pacific and atlantic oceans and then do 24 set intersection on them to return the set where both oceans 25 are reachable. 26 """ 27 m, n = len(matrix), len(matrix[0]) 28 29 if not matrix or not matrix[0]: 30 return [] 31 32 pacific = deque() 33 atlantic = deque() 34 35 for i in range(m): 36 pacific.append((i, 0)) 37 atlantic.append((i, n - 1)) 38 for i in range(n): 39 pacific.append((0, i)) 40 atlantic.append((m - 1, i)) 41 42 def inbounds(y, x): 43 return 0 <= y < m and 0 <= x < n 44 45 def bfs(q): 46 reachable = set() 47 while q: 48 y, x = q.popleft() 49 reachable.add((y, x)) 50 for dy, dx in [(0, 1), (1, 0), (-1, 0), (0, -1)]: 51 new_y, new_x = dy + y, dx + x 52 if not inbounds(new_y, new_x): 53 continue 54 if (new_y, new_x) in reachable: 55 continue 56 if matrix[new_y][new_x] < matrix[y][x]: 57 continue 58 q.append((new_y, new_x)) 59 return reachable 60 61 return list(bfs(pacific) & bfs(atlantic))
def
pacificAtlantic(self, matrix: list[list[int]]) -> list[list[int]]:
7 def pacificAtlantic(self, matrix: list[list[int]]) -> list[list[int]]: 8 """ 9 This question asks us to find the tiles which can reach both the pacific 10 and atlantic ocean, where the pacific is the left and top edge and 11 the atlantic is the bottom and right edge. Water flows from tiles if it has 12 at least the same height or is greater. 13 14 To do this, we can first create two queues, one for the pacific and atlantic 15 oceans, and then add in the reachable edges for both. 16 17 Next, we BFS from both queues. We first create a set that holds the reachable 18 items, and then for each queue, we check to see if we can reach any new nodes 19 by checking its neighbors and making sure its inbounds, reachable, and 20 the the new value is smaller than our current x and y coordinates. 21 If this is correct, we append it to the queue. 22 23 We do this BFS for both the pacific and atlantic oceans and then do 24 set intersection on them to return the set where both oceans 25 are reachable. 26 """ 27 m, n = len(matrix), len(matrix[0]) 28 29 if not matrix or not matrix[0]: 30 return [] 31 32 pacific = deque() 33 atlantic = deque() 34 35 for i in range(m): 36 pacific.append((i, 0)) 37 atlantic.append((i, n - 1)) 38 for i in range(n): 39 pacific.append((0, i)) 40 atlantic.append((m - 1, i)) 41 42 def inbounds(y, x): 43 return 0 <= y < m and 0 <= x < n 44 45 def bfs(q): 46 reachable = set() 47 while q: 48 y, x = q.popleft() 49 reachable.add((y, x)) 50 for dy, dx in [(0, 1), (1, 0), (-1, 0), (0, -1)]: 51 new_y, new_x = dy + y, dx + x 52 if not inbounds(new_y, new_x): 53 continue 54 if (new_y, new_x) in reachable: 55 continue 56 if matrix[new_y][new_x] < matrix[y][x]: 57 continue 58 q.append((new_y, new_x)) 59 return reachable 60 61 return list(bfs(pacific) & bfs(atlantic))
This question asks us to find the tiles which can reach both the pacific and atlantic ocean, where the pacific is the left and top edge and the atlantic is the bottom and right edge. Water flows from tiles if it has at least the same height or is greater.
To do this, we can first create two queues, one for the pacific and atlantic oceans, and then add in the reachable edges for both.
Next, we BFS from both queues. We first create a set that holds the reachable items, and then for each queue, we check to see if we can reach any new nodes by checking its neighbors and making sure its inbounds, reachable, and the the new value is smaller than our current x and y coordinates. If this is correct, we append it to the queue.
We do this BFS for both the pacific and atlantic oceans and then do set intersection on them to return the set where both oceans are reachable.
def
test():