Pacific Atlantic Water Flow

2 min read
LC-Hard

Oct 21, 2022

3 years ago

LeetCode

Solution

Maintain two sets, atl and pac which contains of coordinates that can trickle down to atlantic and pacific oceans respectively
We know that all the borders of the grid can by default flow to the ocean that they border
Solve this problem from the outside in, instead of checking if every single coordinate can travel to the ocean, start from the borders, since we know by default all of them can flow to the ocean
Do a Depth-first Search starting on every coordinate on the border:
- First row: Use the pac set because the first row can by default only reach pacific ocean
- Last row: Use the atl set because last row can by default only reach atlantic ocean
- First column: Use the pac set
- Last column: Use the atl set
After doing a DFS on these first borders, check each coordinate in the entire matrix by looping and if a coordinate is present in both the pac and atl sets, it means it can flow to both oceans, so add it to the answer.

Time	Space	Explanation
`O(mn)`	`O(mn)`

def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]: pac, atl = set(), set() nrows, ncols = len(heights), len(heights[0]) def dfs(r, c, vis): if (r, c) not in vis: vis.add((r, c)) for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]: nr, nc = r + dr, c + dc if nr >= 0 and nr < nrows and nc >= 0 and nc < ncols and (nr, nc) not in vis and heights[nr][nc] >= heights[r][c]: dfs(nr, nc, vis) for r in range(nrows): dfs(r, 0, pac) dfs(r, ncols - 1, atl) for c in range(ncols): dfs(0, c, pac) dfs(nrows - 1, c, atl) ans = [] for r in range(nrows): for c in range(ncols): if (r, c) in pac and (r, c) in atl: ans.append([r, c]) return ans