1219. Path with Maximum Gold | Backtracking | Recursion

[@ARYANMITTAL]

14 + 9 is 23 & not 24 🌚 Complete Backtracking Guide - kzbin.info/www/bejne/ooPMfnqliLF2na8

[@SaurabhSingh-fw1qn]

Bhai exceptional skills !!!

[@thehappydeveloperguide]

Very good. Thank you !

[@adityajhunjhunwala9739]

bro 3 ^ 25 will give TLE then how it can be the Time Complexity

[@bhavaygoel]

hey aryan, glad you are fine! nice vid

[@subhashreddy5391]

Great Explanation, But I didnt get the reason why we can't apply DP? Could you please clarify?

[@ARYANMITTAL]

For Dp we memoize something, that is something which is being repeated again and again, in these kind of 4 directional traversal problems when there is no parameter to go uni - directional, then there is nothing we can memoize ( memoize needs some start point, from which we store answer), here firstly we try every start point & second try all possibilities as everything is different & for a path answer, it is already stored and returned via a dfs. Longest increasing path in a matrix, it is a good problem to compare and see what directional traversal in 4 directional traversal looks like. I hope that explains ❤️❤️

[@subhashreddy5391]

@@ARYANMITTAL Definitely. Thank You!

[@paras6079]

Bhai Square Root Decomposition kya hota hai ? Video bana sakte ho. Iski importance hai kya waise OA's ke liye ? i think ye Query wale problems ke liye use mein aati hai

[@rohit_700]

Aryan Bro, The explanation is as always good. I have one doubt, why are you taking dx and dy array with four values?? let's say my current i=1 , j=1; and dx=-1 and dy =-1 Then accourding to your logic ni = 1-1 =0 ny = 1-1 =0 from (1,1) -> (0,0) we have to take the horizontal path, which is not allowed. for (1,1) you can only choose to go to below valid points up (0,1) down (2,1) left (1,0) right (1,2) can you please explain this??

[@rohit_700]

Okay, that is not double for loop. so it will only take value sin single pass.

[@codencode5546]

You'll never encounter a diagonal value because we are going in only 4 direction. and there is no such pair of {dx,dy} which leads to {-1,-1}

[@worldofgaming748]

I praise you for explaining this clearly but when i see moments like this 13:49 ill be like Nah bro🐼

[@anshadarsh1194]

why are we suning dx and dy stuff containing 0,1 and -1 ??

[@kandariarjun]

To go to the 4 diff directions.

[@aizad786iqbal]

bfs approach please ?

[@gilfoyle2211]

chalo zinda hai Aryan😂😂😭😭

[@ARYANMITTAL]

🕵

[@mukulkhanna5071]

I have solved this problem by creating visited array for each i,j but it is failing here is the code please let me where i am going wrong class Solution { public: int n,m; vectorgr; vectordirs={{0,1},{0,-1},{1,0},{-1,0}}; int dfs(int i,int j,bool vis[16][16]){ if(i=n||j=m||gr[i][j]==0||vis[i][j]==true)return 0; vis[i][j]=true; int ans=gr[i][j]; int maxi=0; for(int k=0;k

[@vikaskumarnitrr]

what is wrong in this code 45 test case passed class Solution { public int getMaximumGold(int[][] grid) { int ans = 0; for(int i=0; i

[@LOKESHE-wi2yd]

is that the testcase had output as 60 and did you got 58 or what

[@LOKESHE-wi2yd]

maybe its because we are marking the visited of a cell as true that not actually yet visited in current path , i too made the same mistake public int dfs(int[][]grid,boolean[][]visited,int r,int c,int sum){ if(r=grid.length||c=grid[r].length){ return sum; } if(visited[r][c]||grid[r][c]==0){ return sum; } visited[r][c] = true; sum+=grid[r][c]; return Math.max( dfs(grid,visited,r+1,c,sum), Math.max(dfs(grid,visited,r-1,c,sum), Math.max(dfs(grid,visited,r,c+1,sum), dfs(grid,visited,r,c-1,sum) ) ) ); }

[@LOKESHE-wi2yd]

class Solution { public int getMaximumGold(int[][] grid) { int ans = 0; for(int i=0; i

[@sivalokesh3997]

@@LOKESHE-wi2yd Good find bro.

[@sivalokesh3997]

20+2+4+7+6+5+3+4+3+1+5. This is the Path for Answer. For your failed testCase. Now understand yourself where it can go wrong.