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
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
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
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.
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
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
Great explaination. There can be a Space efficient solution with this approach as well. Instead of two visit set we can use a m*n matrix initially filled with 0. I'll go through the loops to describe how could we identify the resultset at the end. To mark a cell visited : cell value = Old value + 1 + filler value - Before first iternation, all the visited matrix elements have a value of 0 - In first iteration, where we go through the reverse flow of Atlantic ocean we can pass a filler value of 0. At the end, we will have two unique values 0 or 1. - In second iteration for the pacific ocean, we can pass filler value of 10. At the end, we will have 4 unique values, 0, 1, 11, 12. - O signifies the cells whose water doesn't reach ocean. 1 and 11 specify the cells whose water goes to Atlantic or Pacific ocean respectively. Cells with value 12 are the ones whose water reaches both the oceans. - We can visit the matrix and collect all the cells with value 12.
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))"
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.
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!
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.
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
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...?
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.
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.
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.
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)
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])
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
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.
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.
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!
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?
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
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
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)?
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?
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.
@@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
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.
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.
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
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
@@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.
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
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!
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.
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.
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.
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
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?
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.
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)
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) ?
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
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.
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.
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.
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
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
@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).
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.
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.
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.
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?
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
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
@@zen5882 yeah exactly , i have solved similarly using island problem
```
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
provide 150problems list in a spreadsheet
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
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.
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
these are really not hard at all if you've done enough graph problems
IKR
For returning the common item from both set what we can do is: return atl & pac . I think '&' operator is bit easy.
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.
@@florianhoppe3872 LC does not care about order in this case.
Also pac.intersection(atl) using set theory
you would use the bitwise OR operator if you want both atl and pacific
Excellent video as always :)
Lines 25 to 30 can be replaced with the following
return list(pac.intersection(atl))
Python is amazing :D
As im thinking go to every node and do dfs, my god called me naive :(
God called us naive but this Savior actually tells how to fix ourselves!
we can do that as well
Do that with Memoization, should be pretty comparable, and as that more natural and intuitive aswell.
I did it with backward dfs (ie start from the ocean coast and backtrack)
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
This problem feels more like a gaming interview question, it's pretty cool
I had the same happy idea about this problem and I thought it was kind of a bad solution, but I'm glad it was the correct one! Thanks for your help!
Great explaination. There can be a Space efficient solution with this approach as well. Instead of two visit set we can use a m*n matrix initially filled with 0. I'll go through the loops to describe how could we identify the resultset at the end.
To mark a cell visited : cell value = Old value + 1 + filler value
- Before first iternation, all the visited matrix elements have a value of 0
- In first iteration, where we go through the reverse flow of Atlantic ocean we can pass a filler value of 0. At the end, we will have two unique values 0 or 1.
- In second iteration for the pacific ocean, we can pass filler value of 10. At the end, we will have 4 unique values, 0, 1, 11, 12.
- O signifies the cells whose water doesn't reach ocean. 1 and 11 specify the cells whose water goes to Atlantic or Pacific ocean respectively. Cells with value 12 are the ones whose water reaches both the oceans.
- We can visit the matrix and collect all the cells with value 12.
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))"
return list(pac & atl)
I dont think even list casting is required here. simply return pac & atl
BTW, amazing explanation by @NeetCode
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?
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.
@@nikhil_a01 both intersection() and & have the same performance if applied on sets.
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
Or just iterate over one and check if value present in other. No need nested loop.
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!
Figured it out with the brute force method but didn't even think of this smart solution, thanks!
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.
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.
@@anmollalit Right. If this problem is a strictly increasing water flow, then the dp method will work.
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
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...?
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.
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
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.
was it accepted by leetCode? or you got a TLE?
@@Varuns36 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.
@@Varuns36 it got accepted, but yeah, not very efficient
This time I really enjoy your solution and the abstraction you did. Thank you!
Thanks!
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.
Your thought is right just find intersection of the 2 sets , that would be a solution
The concept and leetcode description given for this problem is so dumb. Great video as usual!
You could have used -1 for the initial heights since the "prevheight" is the ocean.
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)
In the end you could `&` both sets to get common directly.
common = pac & atl
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])
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
crystal clear, Neet is always the best！
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.
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.
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!
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
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?
For the initial edge calls to dfs you could simply pass in the value 0 since the constraints say the heights are >= 0
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
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
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)?
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?
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 :)
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.
@@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
@@TensorWave What is the underlying cost of the intersection method?
@@bertramusb8162 It would be min(m,n) , Because intersection can at max give the smaller set as the result .
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
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.
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.
@@劉兆鵬-y1w Do you mind sharing codes here so people can learn something different here?
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
You can replace line 25 to 30 with "return atl & pac"
🤯
Damn, that is neat
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
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
Same for me
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.
yup, i really don't understand what this doesn't work with DP. Keep failing one or two coordinates on test 107
@@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.
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
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!
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.
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.
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.
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
def isval(i,j,curr):
if i>=0 and i=0 and j
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
really like your videos!! they help me a lot
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.
I spent like 2 hours trying to solve it and nothing. Here I am watching the solution for it 😢😢
its okay !
your videos are the best
Holy cow that solution was so brilliant. I feel like I understood it the whole way through. Thanks for all your hard work
thank you so much💕
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?
you can also do pac.intersection(atl)
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?
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.
Because we use a Set to keep track of visited nodes, you never visit the same node again even with recursive calls.
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)
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!
i think you can check if r and c are in range(rows) like you did in another video
Why should we go to all 4 directions while we have either Atlantic and Pacific oceans only on two sides?
Nice solution. I wonder if BFS would be more elegant or straightforward.
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
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.
@@tylerwomack4178 I think they mean something like INNER JOIN, where only items in both sets are returned
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) ?
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
[grid.size()-1][0] and [0][grid[0].size()-1] are always at atlantic and pacific
explanation is great, but didnt get it why this quesion is under Graph tag. it is kinnda more close to Matrix i guess.
seems more natural to do multisource bfs here?
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.
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.
this solution made me cry , I was trying to do the dfs solution for 1 : 30 hrs but was unable to get the result.
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.
The final nested loops can be replaced by "return pac & atl"
The time complexity of the brute force by dfs/bfs is O((M+N)xMxN) not (N.M)^2
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.
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
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
What if I check the whole column i and row j for heights[j][i]
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
thank you soo much
Great solution
Can you pls explain me the syntax for r
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
@@salczar thank you
Thanks man.. I was thinking about this problem for 2 days and then gave up :(
damn bro 2 days... wtf
Can you please explain why dp doesn't work here. Thanks
@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).
@@sentinel-y8l Thanks, your explanation helped a lot
You are best...!!!
Beautiful!
You're amazing!
This one is petty complex
list(set.intersection(pacific,atlantic)) is faster
No, that will give u a sublist of list, which is not desirable output
wait wtf, this was not that hard as I thought. F**k, aint no FAANG hiring me🙃😭
wow this was so easy I feel dumb that I was not able to figure it out
why is it if the cell is less than the previous height then return?
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.
This is a hard one
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
why dint u explain negative scenario and how will u address it if we reach one in drawing explanation dude!
Finals solved this on my own after 3 days lmao.
Made this problem work with dfs but realised same heights are included so couldnt finish it ...
yea if same heights weren't included I think the dp solution is way easier bc there wouldn't be a cyclic dependency
i find bfs solution to be a lot more understandable
In python, we are better off using list(pac.intersection(atl)) instead of nested loop
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.
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.
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?
@@johnnychang3456 I think leetcode is normalising the tuples into arrays when doing the comparison automatically
This was painful to code in c++. On the other hand I'm really good at converting python to c++ now
Okay, in the brute force, how is it O(m * n) ^ 2 ?
Because DFS is O(m*n) and you run it on each cell. Therefore m*n * m*n
What about traversing the grid in a spiral from (0,0) toward the center. No dfs/recursion needed.
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
@@aymoney81 Thanks you're right.
I'm sure... if we do the brute force ... its a reject... what do you think?