Pacific Atlantic Water Flow - Leetcode 417 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Twitter: / neetcode1
Discord: / discord
⭐ BLIND-75 SPREADSHEET: docs.google.com/spreadsheets/...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
Problem Link: neetcode.io/problems/pacific-...
0:00 - Read the problem
1:08 - Drawing Explanation
8:45 - Coding Explanation
leetcode 417
This question was identified as a facebook interview question from here: github.com/xizhengszhang/Leet...
#graph #dfs #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[@NeetCode]

🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

[@zen5882]

Why can't we just do DFS or BFS through the matrix with visited sets? That'd be a common first thought. I don't know why you would just skip the explanation for why you think it doesn't work

[@sakshamgupta1475]

@@zen5882 yeah exactly , i have solved similarly using island problem

[@sakshamgupta1475]

``` class Solution: def pacificAtlantic(self, heights): R,C = len(heights) , len(heights[0]) seen=set() dirs=[(1,0),(-1,0),(0,1),(0,-1)] res=[] def isPacific(row,col): return col==0 or row==0 def isAtlantic(row,col): return col==C-1 or row==R-1 def checkFlow(row,col): visited=set() atlantic, pacific=False,False queue=deque() queue.append((row,col)) visited.add((row,col)) while queue: row , col = queue.pop() if (row,col) in seen or (pacific and atlantic): return True if isPacific(row,col): pacific=True if isAtlantic(row,col): atlantic=True for dx, dy in dirs: currRow , currCol = row + dx , col + dy if 0

[@rafishaik2496]

provide 150problems list in a spreadsheet

[@jeffrythename5885]

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

[@supercarpro]

God called us naive but this Savior actually tells how to fix ourselves!

[@jugsma6676]

we can do that as well

[@dorondavid4698]

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

[@md.shazidalhasan6726]

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

[@florianhoppe3872]

true, but I don't think the order of the cells would be correct. LC wants it in the same order as they appear in the grid.

[@pikus7450]

@@florianhoppe3872 LC does not care about order in this case.

[@introspectiveengineer392]

Also pac.intersection(atl) using set theory

[@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

[@sreevishal2223]

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))"

[@TCErnesto]

return list(pac & atl)

[@thetechchronicles]

I dont think even list casting is required here. simply return pac & atl BTW, amazing explanation by @NeetCode

[@dbalatero]

If the pac/atl sets contain (row, col) tuples, don't you have to convert then to [row, col] lists to satisfy the output format?

[@nikhil_a01]

If you want to properly satisfy the output format by converting tuples to lists, [list(x) for x in pac & atl] is more concise than what NeetCode did. But it does create a temporary set for the intersection. For clarity, intersection() is better than &. I doubt most people have the set operators memorized.

[@animeshsinghchouhan]

@@nikhil_a01 both intersection() and & have the same performance if applied on sets.

[@ma_sundermeyer]

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

[@directorfaden]

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

[@houmankamali5617]

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!

[@MichaelShingo]

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

[@dimitrisfassois6467]

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.

[@varswe]

was it accepted by leetCode? or you got a TLE?

[@MTX1699]

@@varswe I think it did work that's why @dimitrisfassois6467 mentioned it here. However, the fact that it performs poorly is a point to be noted.

[@ChanChan-pg4wu]

crystal clear, Neet is always the best！

[@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

[@jeetak47]

Or just iterate over one and check if value present in other. No need nested loop.

[@boluo4790]

really like your videos!! they help me a lot

[@msnhao]

I was able to get dfs to work, but at each step, you also have to do a bfs to get every coord with the same height as well

[@CodeDankula]

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

[@yuqichen5262]

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.

[@anmollalit]

In graph Problems, DP Memoisation does not work in cyclic structures. It has to be a DAG for dp to be applicable or we can't apply DP.

[@lemonke8132]

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

[@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.

[@caydauden]

class Solution: def __init__(self): self.grid = [] self.pacific_nodes = set() self.atlantic_nodes = set() self.num_cols = 0 self.num_rows = 0 self.pvisited = set() self.avisited = set() def can_flow(self, node1, node2): r,c = node1 r1, c1 = node2 if r1 self.num_cols-1 : return False if r self.num_cols-1 : return False return self.grid[r][c] >= self.grid[r1][c1] def can_do_ap(self, node, search): r, c = node #if (r,c) == (37,6): # print('debug') if search == 'pacific': yes_nodes = self.pacific_nodes visited = self.pvisited else: yes_nodes = self.atlantic_nodes visited = self.avisited if node in yes_nodes: return True if node in visited: return False if (search == 'pacific' and (r == 0 or c == 0)) or ( search == 'atlantic' and (r == (self.num_rows-1) or c == (self.num_cols-1))): yes_nodes.add(node) visited.add(node) return True visited.add(node) directions = ((0, 1), (0, -1), (1, 0), (-1, 0)) done_neighbors = [] for x, y in directions: neighbor = (r + x, c + y) if self.can_flow(node, neighbor): if self.can_do_ap(neighbor, search): yes_nodes.add(node) for x1, y1 in directions: neighbor1 = (r + x1, c + y1) if self.can_flow(neighbor1, node): yes_nodes.add(neighbor1) return True done_neighbors.append(neighbor) return False def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]: self.grid = heights self.num_rows = len(self.grid) self.num_cols = len(self.grid[0]) self.results = [] for r in range(self.num_rows): for c in range(self.num_cols): if self.can_do_ap((r,c), 'pacific') and self.can_do_ap((r,c), 'atlantic'): self.results.append([r,c]) return self.results

[@jackscott4829]

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

[@vineethsai1575]

In the end you could `&` both sets to get common directly. common = pac & atl

[@camoenv3272]

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

[@mattmendez8860]

Why, though? Your time complexity will be higher in practice and the space complexity will also be higher. Comparing two boolean values across two separate arrays rather than doing a set intersection is most likely going to be less efficient, no...?

[@skyerichardson4692]

You can just do return pac.intersection(atl) at the end instead of iterating through the whole matrix again and writing to a result array :)

[@user-bj5pn1tf7o]

The intersection method will return a 'sub tuple' list which is different from the sample output demo 'sub list' list. I think this is why neetcode use loop to form the output.

[@TensorWave]

@@user-bj5pn1tf7o you can simply convert it into list of lists with linear time. looping over the whole grid is O(m*n) which is very costly compared to linear intersection

[@bertramusb8162]

@@TensorWave What is the underlying cost of the intersection method?

[@dss963]

@@bertramusb8162 It would be min(m,n) , Because intersection can at max give the smaller set as the result .

[@AlexN2022]

Also surprising that in C++ recursive DFS is faster than iterating using std::stack. Although this one I can explain to myself. Just didn't expect it.

[@sunginjung3854]

your videos are the best

[@purerealm]

it could be useful to add an overlay with a note on the previous heights bug in the middle of the video as it's not immediately clear it is a bug , but appreciate all the useful content!

[@balajeerocks3835]

I looped through all the nodes and checked whether its touching two boundaries((up && right) || (up && down) || (left && right) || (left && down)) or not by using a visited array of size N+2, M+2

[@gigas51]

Why is this method (finding all cells that can flow to pacific, and finding all cells that can flow to atlantic) more efficient than finding all cells that can flow to pacific, then running a DFS from just those cells to see if they can reach atlantic?

[@amruthap6334]

thank you so much💕

[@AlexN2022]

Surprising that, in C++ STL at least, iterating over the whole matrix and doing two set.find() is faster than iterating over all keys in the atlantic set and checking each against the pacific. It seemed as two set look-ups per resulting cell either way, and potentially fewer cells to test (only those present in atlantic versus all present in matrix). But here we are.

[@ajinkyakamat7053]

Are u using std::unordered_set or std::set? Coz unordered_sets tend to have faster look up than iteration for smaller structs. Another way to speed this up is not to store things in a set but use a vector of two values that tell you if the key is in Atlantic and Pacific set. You initialize the vector with all cells as false and change the value to true when u encounter it.

[@jayberry6557]

The only thing I'd improve is to name variables better. 'pacific' is obvious but 'pac' may be confusing when looking quickly at code. Also instead of one big if condition you can make it more readable by splitting conditions with early return

[@darshansimha2166]

You're amazing!

[@DavidDLee]

Nice solution. I wonder if BFS would be more elegant or straightforward.

[@DBagg-zz4ip]

Make sets using comprehension for starting tiles. Run a BFS helper on both to expand them. Return intersection. They should've called this one Continental Divide.

[@briang3498]

Instead of having two loops one for pacific and atlantic side, you can just use one loop, a bit more readable imo for i in range(rows): for j in range(cols): if i == 0 or j == 0: # Top or left edge for Pacific Ocean dfs(i, j, pacific, heights[i][j]) if i == rows - 1 or j == cols - 1: # Bottom or right edge for Atlantic Ocean dfs(i, j, atlantic, heights[i][j])

[@symbol767]

Thank you for this explaination, I kept running into TLE trying to do DFS on every (Row, Column) of the grid. I couldn't figure out how to optimize this problem at all, seeing your solution now, I wouldn't have guessed that sadly... Its really good though thank you, makes perfect sense.

[@user-fm1px3jn8f]

I passed it by running each cell by DFS. Every time I found a cell that can reach both pacific and Atlantic, I put it into a set. So, when I run DFS, if meet a cell in the set, I can put the origin into the result directly, instead of checking the next positions.

[@lxu5148]

@@user-fm1px3jn8f Do you mind sharing codes here so people can learn something different here?

[@sarthakjain1824]

You might be running into a problem when the values is same. I tried to make a visited set for this but it gets too complicated

[@MayankKumar_DataScience]

First Way - Subproblem hint: if heights[row][col] has already been explored during dfs/bfs traversal for let's say current row/column i, j then this information can be saved into a hashmap/dictionary as subproblems. Now during further exploration for let's say new current row/col i', j', if we can again encounter a similar row/column as stored and height[i'][j'] >= height[stored_row][stored_col], then it means this current row can reach both the ocean. So basically subproblem is if an island with less or equal height than the current island (to be explored), is able to reach both the ocean, then the current larger island will must be able to reach as well.

[@vijethkashyap151]

Beautiful!

[@hwang1607]

i think you can check if r and c are in range(rows) like you did in another video

[@MotleyVideos]

You can replace line 25 to 30 with "return atl & pac"

[@darshansimha2166]

🤯

[@msugal]

Damn, that is neat

[@honeybadger916]

I was actually able to do this with dynamic programming, but keep failing on some testcase where i missed only on 1 coordinate(i dont know why). But neetcode's approach is better because it is much more shorter and understandable than my code lol

[@HeinekenLasse]

Same for me

[@vishalpoddar]

Same for me. I thing it has to do something with the setting of visited at the beginning of DFS. Wrong and in 106th testcase.

[@juggles5474]

yup, i really don't understand what this doesn't work with DP. Keep failing one or two coordinates on test 107

[@illu1na]

​@@juggles5474 i had similar problem. It was due to "cycle" i.e assume we have [[100, 1, 1, 1], [1, 3, 15, 20]] When we run DFS on (2, 2), it would end up being TRUE and added to the result set. But if (2, 1) is run before (2, 2) and if you are setting default values of atlantic[(2,1)], pacific[(2,1)] to be False in the beginning. (2, 2) can only reach pacific via (2, 1) but we start calculating at (2,1). So dfs(2,1) -> dfs(2, 2) and dfs at (2,2) does not call dfs(2,1) - otherwise there is a cycle - and (2, 2) would yield False and stored in DP.

[@illu1na]

I had to do something like the below with the visited set. I did not have this set originally and relied on just atlantic and pacific sets but that had problem i described above. There is a need to not store partial DP solution that would have a cycle. I did that by only storing True value in the recursion. class Solution: def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]: result = [] n = len(heights) m = len(heights[0]) atlantic = {} pacific = {} visited = set() def dfs(i, j): if (i,j) in visited: return False if (i, j) in atlantic and (i, j) in pacific: return atlantic[(i, j)] and pacific[(i, j)] visited.add((i, j)) for x, y in [(i-1, j), (i, j-1), (i+1, j), (i, j+1)]: if x in range(n) and y in range(m) and heights[i][j] >= heights[x][y]: dfs(x, y) if (x, y) in atlantic and atlantic[(x, y)]: atlantic[(i, j)] = True if (x, y) in pacific and pacific[(x, y)]: pacific[(i, j)] = True visited.remove((i, j)) if (i, j) not in atlantic or (i, j) not in pacific: return False return atlantic[(i, j)] and pacific[(i, j)] for i in range(n): pacific[(i, 0)] = True atlantic[(i, m-1)] = True for j in range(m): pacific[(0, j)] = True atlantic[(n-1, j)] = True for i in range(n): for j in range(m): if dfs(i, j): result.append([i, j]) else: pacific[(i, j)] = False if (i, j) not in pacific else pacific[(i, j)] atlantic[(i, j)] = False if (i, j) not in atlantic else atlantic[(i, j)] return result

[@varswe]

thank you soo much

[@galanafai9487]

Great solution

[@hwang1607]

you can also do pac.intersection(atl)

[@RickusDomesticus]

Yeah apparently I tried to save the result for each block to optimize the dfs, but unfortunately in a case like a whole matrix has the same number, it wouldn't work

[@andreytamelo1183]

Thanks!

[@IMC5776]

If we start from the edges of the graph and dfs inward, why do we want to dfs into adjacent nodes instead of looking at nodes that are only horizontal or vertical from the edges? For instance, in the video you mention that we can start at 2 on the pacific side (6:50), then go to 4, then 7 then 1. But why do we want to go to 7 at all when we know there cannot exist a path from 7 to the pacific ocean that goes through 4 and 2?

[@dk20can86]

The DFS DP solution actually works fine too. The only gotcha is that you need to handle cycles and redo any sections of the DFS that were previously unresolvable due to a cycle.

[@craignemeth942]

Can you describe to how to detect "any sections of the DFS that were previously unresolvable due to a cycle" ? I'm pretty sure that's all I'm missing with my DP solution. I'm failing one of the last test cases with one point missing and there's no way I'm manually solving the 30x30 matrix to understand where it breaks for one point.

[@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.

[@dss963]

Your thought is right just find intersection of the 2 sets , that would be a solution

[@illu1na]

Here is my DFS recursion solution. i had similar problem Neetcode described in the video of not finding all solutions. It was due to "cycle" i.e assume we have [[100, 1, 1, 1], [1, 3, 15, 20]] When we run DFS on (2, 2), it would end up being TRUE and added to the result set. But if (2, 1) is run before (2, 2) and if you are setting default values of atlantic[(2,1)], pacific[(2,1)] to be False in the beginning. (2, 2) can only reach pacific via (2, 1) but we start calculating at (2,1). So dfs(2,1) -> dfs(2, 2) and dfs at (2,2) does not call dfs(2,1) - otherwise there is a cycle - and so (2, 2) would not consider its only feasible path and yield False and this false value is stored in DP. I had to use the visited set. I did not have this set originally and relied on just atlantic and pacific sets but that had problem i described above. There is a need to not store partial DP solution that would have a cycle. I did that by only storing True value in the recursion. class Solution: def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]: result = [] n = len(heights) m = len(heights[0]) atlantic = {} pacific = {} visited = set() def dfs(i, j): print(i, j) if (i,j) in visited: return False if (i, j) in atlantic and (i, j) in pacific: return atlantic[(i, j)] and pacific[(i, j)] visited.add((i, j)) for x, y in [(i-1, j), (i, j-1), (i+1, j), (i, j+1)]: if x in range(n) and y in range(m) and heights[i][j] >= heights[x][y]: dfs(x, y) if (x, y) in atlantic and atlantic[(x, y)]: atlantic[(i, j)] = True if (x, y) in pacific and pacific[(x, y)]: pacific[(i, j)] = True visited.remove((i, j)) if (i, j) not in atlantic or (i, j) not in pacific: return False return atlantic[(i, j)] and pacific[(i, j)] for i in range(n): pacific[(i, 0)] = True atlantic[(i, m-1)] = True for j in range(m): pacific[(0, j)] = True atlantic[(n-1, j)] = True for i in range(n): for j in range(m): if dfs(i, j): result.append([i, j]) else: pacific[(i, j)] = False if (i, j) not in pacific else pacific[(i, j)] atlantic[(i, j)] = False if (i, j) not in atlantic else atlantic[(i, j)] return result

[@illu1na]

hey but my runtime is 1773 where as neetcode's solution is 255ms. so clearly I am missing something here, i thought the time complexity would be the same

[@illu1na]

It is probably due to the fact that i am not saving any False result in the dfs. Still hard to do complexity analysis here. The worst case then would be where all DFS is false and so i have to iterate same cells over and over again and its O(nm * nm)?

[@noelcovarrubias7490]

I spent like 2 hours trying to solve it and nothing. Here I am watching the solution for it 😢😢

[@chidam333]

its okay !

[@michaelgranger3293]

The final nested loops can be replaced by "return pac & atl"

[@netraamrale3850]

You are best...!!!

[@brm266]

The time complexity of the brute force by dfs/bfs is O((M+N)xMxN) not (N.M)^2

[@vinaygoswami5374]

this solution made me cry , I was trying to do the dfs solution for 1 : 30 hrs but was unable to get the result.

[@onlineservicecom]

I am thinking you can improve this by using join two sets in the end instead of go though every point in the grid again

[@tylerwomack4178]

If you joined the two sets, wouldn't you have a new set that has some values that go to one ocean, but not both? It wouldn't be a solution set.

[@bertramusb8162]

@@tylerwomack4178 I think they mean something like INNER JOIN, where only items in both sets are returned

[@hanif3661]

explanation is great, but didnt get it why this quesion is under Graph tag. it is kinnda more close to Matrix i guess.

[@mohakparekh8671]

For brute force how is the time complexity O((N*M)^2) ? Here, we are traversing the whole grid of size N*M. So, the DFS will be called for N*M time. Time complexity of DFS is O(N + 2E). So how it is O((N*M)^2) ?

[@jugsma6676]

This one is petty complex

[@hemesh5663]

Hey, I know this is not great optimization but still as we are using a set can we take the intersection of sets and turn it into a list and operations on sets are quite faster. Please do correct me if I am wrong.

[@johnnychang3456]

Yea set intersection passes the leetcode test. However I am curious why list of tuples == list of list? Is this a python thing? Or it's leetcode treating them as identical?

[@jamesmandla1192]

@@johnnychang3456 I think leetcode is normalising the tuples into arrays when doing the comparison automatically

[@user-hi8jj5ro3g]

Can you pls explain me the syntax for r

[@salczar]

It’s checking out of bounds conditions or if the height you’re trying to get to is smaller than current height….that means you can flow downhill

[@user-hi8jj5ro3g]

@@salczar thank you

[@swastik07]

What if I check the whole column i and row j for heights[j][i]

[@kitkarson4226]

Thanks man.. I was thinking about this problem for 2 days and then gave up :(

[@tanmaysinghal8370]

damn bro 2 days... wtf

[@Terszel]

Had a solution within like 1 minute of watching this and thought its too easy so I try to do it in O(1) space but 2 hrs later still no luck

[@thatguy14713]

Don't get how its O(m*n). Aren't you doing DFS for each border cell? If that's the case then isn't it O(m*n)^2?

[@halahmilksheikh]

I think it's O(m*n). For example, each pacific dfs uses the same pacific set and never gets reset. So in effect, the first pacific dfs will explore a bunch of nodes but the next searches will find less and less because of the common set. If we used a different set after each pacific dfs, then I would agree with you. But because we use the same one, we never have to do repeated work.

[@atd233]

Because we use a Set to keep track of visited nodes, you never visit the same node again even with recursive calls.

[@LightningSpeedtop]

it is actually O (2 *m*n) simply because we never reset the visited set at each iteration, so assuming we have an example for the pac set, and in the first iteration we visited all nodes, every other iteration will never work since the node would already be in visited, hence it would return quickly, likewise for the atl set, so worst case is O(2*m*n) which is O(m*n)

[@ronshen2453]

Isn't the time complexity O(m * n * (m+n))? Because one search takes O(m*n) time and we are doing 2(m+n) such searches.

[@richard12345789]

why dint u explain negative scenario and how will u address it if we reach one in drawing explanation dude!

[@YouTube_Staff]

I didn't understand the question and just looked at your video for 3-4 minutes and was able to solve it perfectly, thank you!

[@yanco6]

This is the Claver way to do it as you ask with one loop: class Solution: def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]: res = [] ROW, COLON = len(heights), len(heights[0]) stack = [] # (row, colon, isPacific) visit = [[[False, False] for _ in range(COLON)] for _ in range(ROW)] # [pasific, Atlantic] # fill init stack for r in range(ROW): stack.append((r, 0, True)) stack.append((r, COLON-1, False)) for c in range(COLON): stack.append((0, c, True)) stack.append((ROW-1, c, False)) while stack: row, col, isPacific = stack.pop(0) for r, c in [(row, col-1), (row, col+1), (row+1, col), (row-1, col)]: inMatrix = 0

[@sheetalhablani4848]

Can you please explain why dp doesn't work here. Thanks

[@andrepinto7895]

@Pikachu27 It doesn't work because the cells you can visit from a given cell, depends on the path you took till you reached that cell, if you keep a vis array to avoid cycles. Imagine a board with two layers of 1s around a single 2, if you start in one of middle layer 1s and walk around the 2 and then go to the 2, you will not be able to reach any ocean from there because all the cells around 2 have already been visited. Your path basically created a dead end. But if you were to start at 2 you would be able to reach both oceans (because all the other cells are 1s).

[@jamesmandla1192]

@@andrepinto7895 Thanks, your explanation helped a lot

[@prathamkesarkar]

wow this was so easy I feel dumb that I was not able to figure it out

[@yulingluo6496]

so smart

[@TheGoya]

What about traversing the grid in a spiral from (0,0) toward the center. No dfs/recursion needed.

[@aymoney81]

I don’t think it’ll work. If you encounter a cell that is reached by both oceans, you’d have to go back and update each reachable cell

[@TheGoya]

@@aymoney81 Thanks you're right.

[@djaym7]

list(set.intersection(pacific,atlantic)) is faster

[@jugsma6676]

No, that will give u a sublist of list, which is not desirable output

[@algorithmimplementer415]

Okay, in the brute force, how is it O(m * n) ^ 2 ?

[@halahmilksheikh]

Because DFS is O(m*n) and you run it on each cell. Therefore m*n * m*n

[@manishparab4427]

I'm sure... if we do the brute force ... its a reject... what do you think?

[@homeroserna9983]

This was painful to code in c++. On the other hand I'm really good at converting python to c++ now

[@Mark-nm9sm]

Made this problem work with dfs but realised same heights are included so couldnt finish it ...

[@jamesmandla1192]

yea if same heights weren't included I think the dp solution is way easier bc there wouldn't be a cyclic dependency

[@halcyonramirez6469]

Finals solved this on my own after 3 days lmao.

[@s8x.]

why is it if the cell is less than the previous height then return?

[@rrt19254]

It's because we are starting from the water and checking which item in the grid we can reach to. Since an item in the grid is only moveable to another item when the value in the other one is lesser than the previous one, if we are checking from the water to the item, we have to flip the logic. So checking if something is reachable from water, we check if the current item is bigger than the previous one. Just think about how we can go from water to a certain item in the grid, which would be an opposite direction from description.

[@jeffwei]

I'm surprised nobody has pointed out that your initial "prevHeight" (where you made the minor errors) can (and should) just be zero, since they are flowing from "sea level" and that would actually be more "accurate" than passing in the height of the points you are checking.

[@apoorvwatsky]

In python, we are better off using list(pac.intersection(atl)) instead of nested loop

[@markolainovic]

Just to be (needlessly) pedantic and annoying, that'd return a list of sets, instead of a list of lists. But if we say that doesn't matter, we might as well return pac & atl then.

[@kris5187]

video cards covered output panel. 😅

[@sauravchandra10]

As we say in hindi "feel agya".

[@magesRNTcute]

Maybe you can do O(1) space by making the first DFS pacific only, and mark visited as negative. Then for second DFS atlantic, you set it to 0 if visited and the value was negative. Final answer would be the coordinates of all 0s. You would need two different DFS functions but seems worth it to me. Gonna try this tomorrow.

[@magesRNTcute]

Okay I got a working solution, however for the second DFS I converted from integer to float to mark as visited. Any negative floats were added to answer array. I also had to add 1 to every value in the beginning to eliminate 0's (because negative tracking wouldn't work otherwise). Solution: leetcode.com/problems/pacific-atlantic-water-flow/discuss/1457917/Ruby-DFS-with-O(N*M)-Time-O(1)-Space

[@magesRNTcute]

Only thing is, I'm not sure if changing int to float is constant space. When I tried researching it, it lead me to believe that it is, however if someone knows more about that I'd be interested.

[@callmechocolateboy]

Bro Why don't you provide time and space complexity for each problem at the end??

[@dolphinextreme48]

Neetcode is great but I hate his way of naming variables. Dude probably doesn't care but it makes reading the code that much more difficult.

[@alesblaze4745]

What is the TC and SC of this solution? and how please explain!

[@MegaBeastro]

i find bfs solution to be a lot more understandable

[@yilmazbingol4838]

THERE IS AN ERROR inside `for r in range(ROWS)` for r in range(ROWS): dfs(r,0,pac,heights[r][0]) dfs(r,COLS-1,atl,heights[r][c]) Instead of `heights[r][c]`, should be `heights[r][COLS-1]`. I don't understand how come in both cases question is accepted

[@lomnguyen8598]

The code is missing the 2 corners (upper right, and lower left) which can hit both atlantic and pacific. =)