Google Coding Interview Question - Path With Maximum Gold (LeetCode)

[@AlgosWithMichael]

TIMESTAMPS ---------------------------------------------------------------------------------------------------------------- 00:00:00 - problem overview 00:01:39 - algorithm walk through 00:10:40 - code walk through 00:16:36 - time and space complexity Enjoy :)

[@tofahub]

This channel is so underrated

[@phanichoragudi57]

Much cleaner code than what I have seen out there. Subscribed immediately!

[@AlgosWithMichael]

Awesome to hear, thank you for the support!

[@bazzalseed]

How is the time complexity O(M*N)? If every cell has gold, you will have to do DFS from each single position. That will yield a O(M^2N^2) run time right?

[@AlgosWithMichael]

I think you are right, in the scenario we have gold at every position our DFS would visit all cells. Good catch!

[@nicholase2868]

i was thinking the same thing. M*N for the top level iteration, then M*N for the DFS, so (M*N)^2.

[@ishitachausalkar1567]

@@AlgosWithMichael but chances of that is slim as the number of rows and columns can be 15 x 15 = 225, but they have said that at-most 25 cells can have gold.

[@codingessential91]

since this problem does not have similar subproblems (as max gold from any index depends on from where we are coming), hence we cannot memoize this solution. that is why this is sort of "unoptimised dp" and has exponential time.

[@serhattural3168]

It should be k*(3^k) where k is m*n. We trying to find start point by itareting on the grid(m*n) times. For each start point we have 3 possible direction (exclude prev cell). And the depth can be all grid cells(m*n). this is like starting point grid(1,1) -> [grid(2,1), grid(1,2), grid(0,1), grid(1,0)] repeat this for all childs again.

[@yitingg7942]

hahaha again two mins into watching your video, I fixed my code and got it right. It shows that a great teacher is someone who inspires the students and enlightens them lol. Thank you so much!

[@AlgosWithMichael]

Glad I could help!

[@nitisharma8973]

Michael, you explained it so lucidly. Subscribed and looking forward to see more content like this from you.

[@AlgosWithMichael]

Thank you so much for the support!

[@SelftaughtSoftwareEngineer]

Your explanations are always so clear and easy to understand. Thank you!

[@AlgosWithMichael]

You're very welcome!

[@sukhrobgolibboev]

your explanations are great using the "whiteboard", keep up the great work

[@AlgosWithMichael]

Awesome, thanks for watching!

[@rajat1548]

Great code and a very simple explanation. I immediately subscribed it.

[@AlgosWithMichael]

Awesome, thank you!

[@iamryuzaki]

The time complexity can be reduced from being exponential to N*M if you visit one node only once by making it visited permanently or change gold to zero in the original matrix after visiting it.

[@gauravkungwani]

try doing it, you will get wrong ans. You haven't understood it well.

[@YashTrivedi21]

Thanks for the explanation. I was thinking of some optimization don't know if it would work. What if we make another 2d array of same size and store the Max value for each cell in all 4 directions? So when we visit that cell again we don't have traverse again.

[@rosonerri-faithful]

Great intuition and solution,buddy..keep it up. Thanks for the video

[@chandragirivishnuvardhan7654]

Awesome explanation.Thank you so much for your valuable and catchy explanation.

[@AlgosWithMichael]

You are most welcome

[@ruchikas005]

I recently find out your channel, and it is super amazing. Well done and kudos :-)

[@AlgosWithMichael]

Thank you very much!

[@hotspur217]

Solid explanation mate. Keep doing more videos.

[@AlgosWithMichael]

More to come!

[@fangyizhu8893]

Very clear and easy to understand. Thank you!

[@AlgosWithMichael]

No problem, thanks for watching!

[@ankit_irl]

Clean implementation. Thank you for this

[@AlgosWithMichael]

Of course, anytime

[@biswadeepchakraborty3546]

Hi could you please make a tutorial on this kind of problems from the scratch like how to use this dfs along with these backtracking approach. I mean could you dry run and make a tutorial on this please

[@sivahacker8857]

Thank you so much. We want graphs like that.

[@AlgosWithMichael]

Anytime!

[@satyanarayanmohanty3415]

Brilliant explanation as always.

[@AlgosWithMichael]

Glad you liked it!

[@ayushman_sr]

etf did you did with T.C it will be (r*c)^2 or n^4 ish

[@kumarc4853]

Hey @Michael , Thanks for the video. Question: if there is a new boolean array being passed into the DFS function, is the backtracking on visited cells needed?

[@shikharchaudhary835]

Hey, good explanation, but just one doubt, shouldnt the time complexity be - m*n*3^mn ?

[@jinzituo]

Time complexity should be exponential since this is a classical backtracking problem.

[@vinprabhu]

You deserve more views

[@AlgosWithMichael]

Thank you kindly

[@mardhapuhareesh4553]

Super bro no words to say anything 💯

[@AlgosWithMichael]

Haha awesome man thanks

[@AbhishekSingh-og7kf]

Thanks Michael.🔥

[@_ankit_]

Heyy Michael I was trying to solve same problem and was stuck but then referred to your video and it worked. But I still have some doubts regarding the approach. If I am not writing this last line visited[i][j]=false; then I am getting TLE error, idk why it is happening.

[@AlgosWithMichael]

It's because we need to re-use the position at a later time in our DFS. If we don't set the position marked as true back to false when we finish searching in the path, we may not get the correct solution. In other words, a position can be used for multiple paths in the DFS.

[@_ankit_]

@@AlgosWithMichael no, I m getting correct answer since I didn't pass visited array as reference so when we will back to previos call of function in function call stack the visited array will be at previous state doing same thing as adding that line in your code. But idk why am I getting a TLE error when I submit it.

[@saumyachoudhary863]

@@_ankit_ same i am also getting tle, even I am passing visited with reference and doing visited[i][j]=false and it runs fine if we run that test case while compile and run but when I am going to submit it shows tle. did anyone find the solution to this problem?

[@saumyachoudhary863]

​@@AlgosWithMichael same i am also getting tle, even I am passing visited with reference and doing visited[i][j]=false and it runs fine if we run that test case while compile and run but when I am going to submit it shows tle. did anyone find the solution to this problem?

[@munchika7013]

you should add grid[i][j] in line 27 before returning

[@AlgosWithMichael]

i dont think that is necessary though since we just need to return the max from the directions

[@curesnow6493]

Good explanation! I am still confused about the visited 2d Array, like mark true if visited, then mark false when it is done on the current cell. Can you please explain it to me? Thanks!

[@AlgosWithMichael]

Sure! When we mark the position as true, we are saying that this position has been seen on this path. When we mark the position as false, we are doing backtracking because we are pretty much telling our algorithm that we can now used this previously marked true position that it can be used again in another path. Hope that makes sense!

[@curesnow6493]

@@AlgosWithMichael thanks for your explanation !

[@prithvirajan105]

Thanks... from india..🙌

[@guymograbi]

Checking if i,j cell holds a 0 will make you miss some solutions.

[@munchika7013]

Where do you return grid value? This will always return 0

[@AlgosWithMichael]

I return the maximum of all the directions at the end of the recursive function. That is technically the grid value. Thanks for watching!

[@munchika7013]

@@AlgosWithMichael I tried your exact code and it returns zero for me.

[@ishq_gunah_hai3179]

@@munchika7013 Check the variable declaration i.e. public and private. Get stronger with oops concept. If still you cannot figure out contact me.

[@TheElementFive]

Returns zero for me as well

[@parthkolgiri7501]

Damn, you are smart!

[@natalieweishuhn521]

Something's not working right if translated into python. What did I do wrong here? def getMaximumGold(self, grid): """ :type grid: List[List[int]] :rtype: int """ if grid == None or len(grid) == 0: return 0 maxTotal = 0 m = len(grid) n = len(grid[0]) def dfs(grid, i, j, m, n, visited): #rtype: int #out of bounds return 0 #visited[i][j] == True return 0 #grid[i][j] == 0 return 0 if (i < 0) or (j < 0) or (i >= m) or (j >= n) or (grid[i][j] == 0) or (visited[i][j]): return 0 #start visiting visited[i][j] = True left = dfs(grid, i, j-1, m, n, visited) right = dfs(grid, i, j+1, m, n, visited) up = dfs(grid, i-1, j, m, n, visited) down = dfs(grid, i+1, j, m, n, visited) #done visiting visited[i][j] = False return (max(left, right, up, down)) + grid[i][j] for i in range(m): for j in range(n): visited = [[False]*n]*m if grid[i][j] != 0: gold = dfs(grid, i, j, m, n, visited) maxTotal = max(maxTotal, gold) return maxTotal

[@aasthajain4987]

great explaination!!

[@AlgosWithMichael]

Thank you!

[@chaoschao9432]

very helpful, thanks!

[@AlgosWithMichael]

Glad to hear, thanks for watching!

[@atharvakango7244]

Clean! Awesome!

[@AlgosWithMichael]

Thanks!

[@biaojin5188]

I have not see the running result. can you run it ?

[@AlgosWithMichael]

I run the code at 16:28, is that what you mean?

[@jagrit07]

Thanks, man.

[@AlgosWithMichael]

No problem 👍

[@himanshuchhikara4918]

super amazing explanation sir

[@AlgosWithMichael]

Thank you!

[@anands9407]

hey can u tell me when do i know when do i know it is a backtracking problem

[@anands9407]

btw this was the best explanation of a backtracking problem i've ever seen...keep making videos!even if noone watches i will :P

[@AlgosWithMichael]

I can tell to use backtracking when the problem could have many solutions and at each state you determine if you are on the appropriate path or not. You repeat this process until you get to your goal state. Hope that makes sense!

[@anands9407]

@@AlgosWithMichael yes..but still it is pretty similar to dp right...very often i use dp on backtracking problems and vice versa..how do i distinguish between them

[@AlgosWithMichael]

Yea, there are many problems that involve the use of backtracking, but in addition to that you can use memoization (dp) to solve the problem more effeciently. I suppose those two things go hand and hand, but there are times when cases do not repeat themselves and backtracking must be done without dp.

[@anands9407]

thanks for the help :)

[@katielamber0238]

man I love you ahahah

[@AlgosWithMichael]

Thank you!

[@aishwaryam1052]

Why do we set visited[i][j]=false again?

[@AlgosWithMichael]

To allow for that specific cell to be used in another calculation as the algorithm moves forward.

[@aishwaryam1052]

@@AlgosWithMichael Thank you!

[@ishq_gunah_hai3179]

@@AlgosWithMichael Awesome man 💗

[@AlgosWithMichael]

Thanks!

[@AlgosWithMichael]

Anytime!

[@TheElementFive]

Returns 0 for me..

[@rishavsaha5254]

int dfs(vector&grid,int n,int m,int i,int j) { if(i=n || j=m || grid[i][j]==0) return 0; int val=grid[i][j]; grid[i][j]=0; //So that we cannot again move to this index in this DFS call int a=val+dfs(grid,n,m,i-1,j); int b=val+dfs(grid,n,m,i,j-1); int c=val+dfs(grid,n,m,i+1,j); int d=val+dfs(grid,n,m,i,j+1); grid[i][j]=val; //Backtracking return max(max(a,b),max(c,d)); } int getMaximumGold(vector& grid) { int n=grid.size(),m=grid[0].size(); int maxGold=0; for(int i=0;i

[@shishirarora8808]

O(m * n * 4^(m * n))

[@manasbolt]

why are we doing visited[i][j]=false at the end of the function??

[@AlgosWithMichael]

So that we can re-use that position at a later time in our DFS. If we don't set it back to false, it won't be used again.