Pacific Atlantic Water Flow - Leetcode 417 - Python

0:00 - Read the problem
1:08 - Drawing Explanation
8:45 - Coding Explanation

leetcode 417

#graph #dfs #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[jeffrythename]

As im thinking go to every node and do dfs, my god called me naive :(

[md.shazidalhasan]

For returning the common item from both set what we can do is: return atl & pac . I think '&' operator is bit easy.

[gnaneswarilolugu]

The first time I watched this video, I was absolutely blown away by how brilliant the solution is and went into depression knowing I would have never come up with such solution on my own but then leetcode marks it medium. How in the world am I supposed to solve hard ones. Not in this lifetime

[sreevishal]

Awesome tutorial!!, a kind note -> for checking if a value is present in both set pac and atl we can do it in one line as "return list(pac.intersection(atl))"

[directorfaden]

Excellent video as always :)
Lines 25 to 30 can be replaced with the following
return list(pac.intersection(atl))
Python is amazing :D

[dorondavid]

This problem feels more like a gaming interview question, it's pretty cool

[siddharthmanumusic]

Thanks Neetcode! One simplification you could do - while calling the dfs() functions, we could simply pass prevheight as 0. Assuming the height would never actually be in negative here

[TheChelengo]

Lines 25 to 30 can be reduced to pac & atl since they are both sets you can use & to get only the values that are present in both

[houmankamali]

I think the first approach that you mention i.e. finding the distance of a node to either ocean based on the distance of its adjacent nodes, leads to Floyd Warshall Algorithm which you mention in your common graph algorithms. Thanks!

[dimitrisfassois]

I was able to solve it the first way you mentioned that you weren't sure if it was going to work. I did two DFS traversals starting from each cell, and saved the entire path in case that cell could reach either ocean. In the DFS recursive calls I had one base condition to check if the cell is in the path to an ocean to cut out the repeated work. It works, but it's not very efficient, and the code is very long as well.

[uguook]

just need to call dfs on nodes which are either max in their row or in their col. if they satisfy neither, no need to bother. this soln works

[yuqichen]

Thank you for telling me that brute force with memorization is almost impossible. I spent many hours to figure it out but I failed because I found a dead loop using that method.

[camoenv]

You can also init a matrix of booleans for each ocean at the beginning, rather than adding each coordinate to a set as we loop. Same time/space complexity!

def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
rows, cols = len(heights), len(heights[0])

atlantic = [[False for _ in range(cols)] for _ in range(rows)]
pacific = [[False for _ in range(cols)] for _ in range(rows)]

directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]
def build(ocean, x, y, val):
if 0 <= x < rows and 0 <= y < cols and heights[x][y] >= val and not ocean[x][y]:
ocean[x][y] = True
for d1, d2 in directions:
build(ocean, x+d1, y+d2, heights[x][y])

for i in range(rows):
build(atlantic, i, cols-1, 0)
build(pacific, i, 0, 0)

for j in range(cols):
build(atlantic, rows-1, j, 0)
build(pacific, 0, j, 0)

res = []
for r in range(rows):
for c in range(cols):
if atlantic[r][c] and pacific[r][c]:
res.append([r, c])

return res

[CodeDankula]

Holy cow that solution was so brilliant. I feel like I understood it the whole way through. Thanks for all your hard work

[MichaelShingo]

Figured it out with the brute force method but didn't even think of this smart solution, thanks!

[caydauden]

Here is the code of how I solved it with the first way you mentioned (DFS + DP). There was definitely a problem with this route which was very accurately described by Andre Pinto's reply to Sheetal. However, the fix I had was that for every node that can be marked as flowable to ocean, I also loop its neighbors, and whichever neighbor can flow to this node, I mark the neighbor as flowable to ocean as well. This fixes the dead-end issue. Still not the smartest approach, but just in case anyone is curious.

[lemonke]

You could have used -1 for the initial heights since the "prevheight" is the ocean.

[ma_sundermeyer]

This time I really enjoy your solution and the abstraction you did. Thank you!

[nathanwailes]

I didn't find the conceptual explanation very helpful in this video. The explanation I have in mind for myself (which might not be right) is: we're going to construct two sets, one which contains all positions that can reach the Pacific Ocean, and one that contains all positions that can reach the Atlantic Ocean, and then we're just going to see which positions are in both sets. To fill out these sets, we're going to start at every position adjacent to the oceans and see which positions can reach that adjacent-to-the-ocean position. If we come across a position we've already confirmed can reach a particular ocean, we can skip it in the future because our algorithm will have already explored all of the positions that could reach that position.

[jackscott]

The concept and leetcode description given for this problem is so dumb. Great video as usual!