Path with Maximum Gold - Leetcode 1219 - Python

[@zachandbro]

Always appreciate these videos. You’re such a great explainer when it comes to these complex programming problems

[@MP-ny3ep]

Thank you for the leetcode daily. Really appreciate it.

[@nirmalgurjar8181]

As per constraints given (There are at most 25 cells containing gold) so technically solution turns out to be O(m.n) ~ O(m.n.4^25) for large number of m and n. correct me if my understanding is wrong.

[@ajaysenger2]

Solved it in one go feeling great now.

[@freecourseplatformenglish2829]

Cool dude, I came here to verify my intution and happy that it matches with your solution.

[@kiratsingh2595]

you should put some tags in your videos because i search path with maximum gold your video didn't show up i knew it that you uploaded the video on youtube home page but it didt come up when i searched it , then i searched it by path with maximum gold neetcode even then it didnt show up , so plz use some tags in your videos so that it can reach more people :)

[@jayrathod9271]

class Solution: def getMaximumGold(self, grid: List[List[int]]) -> int: ans ,curr= 0,0 row,col = len(grid),len(grid[0]) def dfs(i,j,curr): if i< 0 or i>=row or j=col or grid[i][j]==0: return t = grid[i][j] grid[i][j]=0 curr += t nonlocal ans dfs(i-1,j,curr) dfs(i+1,j,curr) dfs(i,j+1,curr) dfs(i,j-1,curr) ans = max(ans,curr) curr -=t grid[i][j]=t for i in range(row): for j in range(col): if grid[i][j]!=0: # curr = 0 dfs(i,j,curr) return ans

[@CS_n00b]

I'm not sure what the point of having a visit local variable is since we still need to remove each visited point from the set? Why not just have a global visit set or pass visit.copy() into each dfs instance so we dont need to do visit.remove()

[@yang5843]

Thanks for making this video

[@christophervradis7285]

Thanks Neet

[@varunpalsingh3822]

thank you neet :-)

[@SC2Edu]

Thanks!

[@chien-yuyeh9386]

Nice🎉🎉

[@upsidedownChad]

Bros cooking solving LeetCode left and right

[@bobbywang9223]

Why is this considered DFS? doesn't that only apply to graphs and trees?

[@vuanhkhoa9715]

DFS is a huge topic and not only apply to graph and trees. You can try to draw a decision tree and you will see, at each cell, it will try to go as deep as it can in 4 directions to find the maximum gold it can achieve. That is DFS. And the same for BFS

[@nirmalgurjar8181]

Its everywhere be it recursion, tree, graph, composite object, matrix etc. DFS, BFS are standard and can be reused in variety of problems.

[@cem4960]

the grid in this problem is basically a graph

[@jagrutitiwari2551]

If a cell is removed from visit, isn't there are a chance that it would be visited twice? Can someone explain this?

[@madiyar8079]

It's explained at 6:00 this is exactly what we want, because visited cell can be visited in another backtracking flow and visiting that cell from the different path is valid.

[@rahulsyt_]

when we exit from the call stack, we undo the changes that we made to the grid in the current call stack. And, hence it won't affect to the other calls.

[@nirmalgurjar8181]

This is backtracking, we want to explore all the paths with greatest sum, once current path is evaluated, we want to reconsider same cell of other remaining path. Try drawing the solution for small inputs and figure it out.

[@phanthe3471]

anyway, there are at most 25 gold cells, so the complexity should be 25*(4^25). Please correct me if i miss anything

[@nirmalgurjar8181]

outer 25 will be m*n as in any case we have to run the outer loop m*n times, so m*n*4^25

[@sauravsingh4497]

At first I thought of doing bfs/DFS from every non zero node but thought there must be a more efficient way 🥲