Pacific Atlantic Water Flow - Leetcode 417 - Python

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

[@gnaneswarilolugu2323]

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

[@bian7744]

These graph ones actually have real life use unlike some of the other ones so getting good at these will make you a better engineer that is what I am trying to do.

[@rijulranjan8514]

This is medium if you already understand graphs and have good problem solving intuition. This is easy if you’ve done tons of graph problems and have a high level of problem solving intuition. Similarly it is hard if you are not too familiar with graphs and haven’t built up intuition with them. Keep solving problems and eventually you will most certainly come up with such solutions. I believe in you

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

[@harrywang4769]

you would use the bitwise OR operator if you want both atl and pacific

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

[@shabindersingh9275]

Do that with Memoization, should be pretty comparable, and as that more natural and intuitive aswell.

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

[@directorfaden]

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

[@dorondavid4698]

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

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

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

[@indraxios]

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

[@MTX1699]

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

[@tanmaymathur6833]

@@indraxios it got accepted, but yeah, not very efficient

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

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

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

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

[@MichaelShingo]

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

[@lemonke8132]

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

[@jackscott4829]

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

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

[@jeff4615]

@@anmollalit Right. If this problem is a strictly increasing water flow, then the dp method will work.

[@ma_sundermeyer]

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

[@vineethsai1575]

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

[@devonchia5976]

we could also exclude parsing in previous height argument into dfs func: def dfs(r,c,visited): visited.add((r,c)) for dr, dc in directions: row, col = dr + r, dc + c if (row < 0 or row == ROWS or col < 0 or col == COLS or (row,col) in visited or heights[r][c] > heights[row][col]): continue dfs(row,col,visited)

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

[@JefferyChiang-l3x]

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]

@@JefferyChiang-l3x 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 .

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

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

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

[@illu1na]

Here is my DFS recursion solution. (The one he casually mentions as 4:30) 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)?

[@manalitrivedi8784]

Instead of the last loop, you can also return list(pcf.intersection(atl)) where the intersection gives the common elements of both these sets. But thanks for the amazing solution nonetheless!

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

[@MotleyVideos]

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

[@darshansimha2166]

🤯

[@msugal]

Damn, that is neat

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

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

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

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

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

[@micmaxian]

For the initial edge calls to dfs you could simply pass in the value 0 since the constraints say the heights are >= 0

[@ChanChan-pg4wu]

crystal clear, Neet is always the best！

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

[@劉兆鵬-y1w]

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]

@@劉兆鵬-y1w 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

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

[@noelcovarrubias7490]

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

[@chidam333]

its okay !

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

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

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

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

[@MOHITRANA-to7rf]

[grid.size()-1][0] and [0][grid[0].size()-1] are always at atlantic and pacific

[@kvtys]

I'm conceptually confused by the question here - if water can flow to adjacent cells less than or equal to the cell height (which makes sense in real life), why are we moving water from the pacific and atlantic to cells with greater heights? That's like moving water up a hill - it doesn't make sense to me at all. Isn't the water defying gravity here and going against the question prompt?

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

[@boluo4790]

really like your videos!! they help me a lot

[@DavidDLee]

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

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

[@sunginjung3854]

your videos are the best

[@hwang1607]

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

[@AlanChang-o9k]

Hi NeetCode, I am really confuse about the answer that why would you go 4 dirs if you are only finding the cell is going to PO or AO, for example if you have the code like dfs(0,c,pac,height[r][c], does that mean we should only go to r-1(up) and c-1(left) to reach the Pacific ocean? By the way I do failed about one of the test that : heights = [[1, 2, 3], [8, 9, 4], [7, 6, 5]] and expect result is : [[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]] which [2,1] is not make any sense to me that, [2,1] has the value 6 and 6 is not able to reach the Pacific ocean because it have 7 as left and 9 as top

[@SOMESHKHANDELIA]

I think the time complexity is wrongly told in the video Pacific: (DFS first column) m*(m*n) + (DFS first row) n*(m*n) = (m^2)*n + (n^2)*m Atlantic: (DFS last column) m*(m*n) + (DFS last row) n*(m*n) = (m^2)*n + (n^2)*m Complexity is therefore: O(N^3) and not O(N^2) as suggested by the video.

[@michaelgranger3293]

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

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

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

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

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

[@brm266]

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

[@hwang1607]

you can also do pac.intersection(atl)

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

[@kitkarson4226]

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

[@tanmaysinghal8370]

damn bro 2 days... wtf

[@amruthap6334]

thank you so much💕

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

[@djaym7]

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

[@jugsma6676]

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

[@ajajajaj686]

Why should we go to all 4 directions while we have either Atlantic and Pacific oceans only on two sides?

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

[@draugno7]

In Java time performance is pretty bad when putting/getting pairs of inidices (Pair class), matrixes atlantic and pacific give a much better performance :/ I tried calculating a unique index for set based on two indices but I can't find a way to do it

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

[@jugsma6676]

This one is petty complex

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

[@Specks-e9m]

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

[@Specks-e9m]

@@salczar thank you

[@galanafai9487]

Great solution

[@sachinjain6913]

wait wtf, this was not that hard as I thought. F**k, aint no FAANG hiring me🙃😭

[@andreytamelo1183]

Thanks!

[@netraamrale3850]

You are best...!!!

[@indraxios]

thank you soo much

[@homeroserna9983]

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

[@CS_n00b]

seems more natural to do multisource bfs here?

[@MegaBeastro]

i find bfs solution to be a lot more understandable

[@prathamkesarkar]

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

[@darshansimha2166]

You're amazing!

[@swastik07]

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

[@vijethkashyap151]

Beautiful!

[@manishparab4427]

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

[@AmanjotSingh-rj7ox]

damn, almost came up with the correct approach. but fuck man i love these kind of problems, requires logic and fun not like brainless Dp problems

[@ilanaizelman3993]

This is a hard one

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

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

[@halcyonramirez6469]

Finals solved this on my own after 3 days lmao.

[@richard12345789]

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

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

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

[@sauravchandra10]

As we say in hindi "feel agya".

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

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

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