Path with Maximum Gold | Simplest Explanation | Leetcode 1219 | codestorywithMIK
ฝัง
- เผยแพร่เมื่อ 3 มิ.ย. 2024
- Whatsapp Community Link : www.whatsapp.com/channel/0029...
This is the 12th Video of our Playlist "Backtracking : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve a very standard and simple 2D DFS/BFS traversal problem with a tadka of backtracking array : Path with Maximum Gold | Simplest Explanation | Leetcode 1219 | codestorywithMIK
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Path with Maximum Gold | Simplest Explanation | Leetcode 1219 | codestorywithMIK
Company Tags : GOOGLE
My solutions on Github(C++ & JAVA) : github.com/MAZHARMIK/Intervie...
Leetcode Link : leetcode.com/problems/path-wi...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My Recursion Concepts Playlist : • Introduction | Recursi...
My GitHub Repo for interview preparation : github.com/MAZHARMIK/Intervie...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
The provided approach utilizes depth-first search (DFS) to explore all possible paths starting from each cell containing gold in a given grid. It iterates through each cell in the grid and initiates DFS from cells with non-zero gold values. During DFS, it recursively explores neighboring cells, marking visited cells and accumulating the gold values along the path. Once all possible paths are explored from a cell, it backtracks to explore other paths. The maximum accumulated gold value from all possible paths is returned as the result.
✨ Timelines✨
00:00 - Introduction
00:32 - Problem Explanation
6:10 - Explaining DFS Approach
10:54 - Coding it up
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024
I have been following you for the last 2-3 weeks and frankly speaking your videos are adding a very much significant value in my learning path. Talking about today's question I don't have to see any tutorial as I can solve today's question alone. Then came again to your video to see which approach you are talking about. Your effort / videos are appreciated.
So glad to hear that. Thank you so much ❤️🙏
This channel is a goldmine for learning dsa 🤩
Means a lot ❤️❤️🙏🙏
indeed
You explain with the patience of an angel.
Believe nahi hota ki mai ab aise qns khud se solve karleta hu. I have seen growth in me and the power of consistency. Even if I am busy with my dev related study routine, I give atleast 1-2 hours to DSA. Thanks to you for improving my problem solving skills
love your voice and calmness. I was able to solve this on my own. thanks to you
Was able to do it after seeing your backtracking playlist
bro can u plz provide bfs solution too..or make a video on it ...
btw the explanation was really nice bro..
Great content. Thanks
I solved it because of you. I learned this type of solution from you the island problems.... Thank You Mik. you are so helpful for me and Others. Keep uploading
So glad to hear that. Thank you so much ❤️🙏
Great video as usual
Bhaiya mey bhi DFS se hi approach kiya like question read karte samay hi pata chal gya tha jab wal 4-directions ki baat bola to , 98% faster in java --> my code
class Solution {
// Approach --> DFS
// T.C : O(n*m)*4(k) where k is the count of the gold passibilities
// S.C : O(1) Stack space --> depth of recursion -> 4(k)
int[] roww = {1, -1, 0, 0};
int[] coll = {0, 0, -1, 1};
public int checkIfAllZeros(int[][] grid) {
int count = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] != 0) count += grid[i][j];
else return 0;
}
}
return count;
}
public int backtrack(int[][] grid, int x, int y, int count) {
if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == 0) return 0;
int curr = grid[x][y];
grid[x][y] = 0;
count += curr;
int localMaxGold = 0;
for (int i = 0; i < 4; i++) {
int newX = x + roww[i];
int newY = y + coll[i];
localMaxGold = Math.max(localMaxGold,backtrack(grid, newX, newY, count));
}
grid[x][y] = curr;
return curr + localMaxGold;
}
public int getMaximumGold(int[][] grid) {
int count = checkIfAllZeros(grid);
if (count != 0) return count;
int maxGold = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] != 0) {
maxGold = Math.max(maxGold, backtrack(grid, i, j, 0));
}
}
}
return maxGold;
}
}
Awesome 👍🏻❤️
i have one question bhaiya
vector directions{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
when i used this, i got TLE why ?
and this one works fine.
vector directions{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
This is very similar to unique paths 3, was able to solve this question on my own after seeing that. Thanks man 💙
Indeed ❤️
@@codestorywithMIK vector direction{{-1,0},{1,0},{0,1},{0,-1}}; isko DFS fxn k andar lene se TLE q de rha h...please explain
@@Mohit-fe5hx use &direction
Please make a video on matchstick to square
please also give the optimal approach in the same video. Thank you
At any moment during the DFS traversal, only one path is explored, so only a constant number of function calls are in the call stack.
the depth of the recursion tree can reach up to the total number of cells in the grid in the worst case scenario.
Therefore, the maximum stack space used is the maximum depth of the recursion tree, which is O(m * n).
please correct me if i am wrong ..
i was able to solve this on my own thanks to your awesome teachings .. i have learnt a lot from you.. thanks for making DSA easy and fun
That’s a good point. Yes the recursion stack can grow to m*n in worst case.
@@codestorywithMIK thank you for confirming
bhaiya can you explain that new[i] and new[j] wala lines in detail?
Thanks a lot bhaiya congrats for 47k subs 🥳🥳❤❤
Thank you so much 😀
The greatest ever on youtube!
Means a lot to me 🙏🙏❤️❤️
I was literally laughing "Backtracking jaay bhaad me" 😂😂
bro please make concept playlist on backtracking bhai backtracking ke questions mein pata hi nail chailata kaise karna hai specillay kai questions mein where we use visited mark it false and and once task done make it true agin ye sab kaise paa chata hai ki
questin me vis ko false mark karke true mark karna hai please make playlist and try to explain ki konse scenario mein konsa approach lagega
Hi there,
Sure. But before studying backtracking,
You must study Recursion Concepts - How recursion flow goes and rewinds, how recursion tree progresses etc.
You can see my Recursion concepts - th-cam.com/video/pfb1Zduesi8/w-d-xo.html
Meanwhile, let me soon plan to make one long video which will cover all concepts of backtracking.
Remember that in Backtracking , recursion is heavily used, so make sure to first go through recursion concepts
@@codestorywithMIK tHANKS BRO ya please make 1 long vidoe of backtacking where u cover all the concepts ,patterns and some questions regarding that concept I mean first the concept and pattern and then the releveant this way it would be clear and would allow us to think
then the relevant question to that concept this way it would be clear and would allow us to think
why can't we use here bfs/dfs , please explain in detail?
Khud se ban bhaiya .. thanks for such quality contnet
Sir please phala dp series complete kara do 🙏🏻🙏🏻
I'm trying to understand why we didn't use memoization here? I can sense that there is overlapping problems we keep solving. Think about it from symmetry, if we go a to z in a certain path, z to a can be in that same path but in reverse as well.
No, here we can’t use DP. I should have covered this point in my video. Let me try to explain here.
For a given cell [i][j] , we can have different values depending on the cell from where you started your DFS. so you can’t store any past result in a dp array i.e. you can’t memoize or use previous results to solve your current result. Hence you can’t use DP in such cases.
Everytime you are trying your dfs from different cell from the main double for loop and for each starting cell, every cell [i][j] can have different value. So memoizing value of [i][j] doesn’t make sense here
Hope this helps ❤️❤️❤️
koi iska bfs code share kardo and explaination bhi
solved it myself. but waiting for you..🇧🇩
❤️❤️
@@codestorywithMIK sir, now i can understand hindi well, only for you.
This means a lot me ❤️❤️❤️
So glad to hear this 🙏❤️
@@codestorywithMIK thanks sir ❤️❤️❤️
this is not a graph question so how can we know when to apply bfs and dfs..
also for bfs, how would we approach here, please provide a hint.. I am a bit confused
we won't have recursion in bfs?
Can we solve this problem using dynamic programming?
For a given cell [i][j] , we can have different values depending on the cell from where you started your DFS. so you can’t store any past result in a dp array i.e. you can’t memoize or use previous results to solve your current result. Hence you can’t use DP in such cases.
Bro Bit Manipulation playlist bhi bana start kr do
Let me start that soon.
Currently very occupied in some project ❤️😇
@@codestorywithMIK Okay brother.
BFS toh main tha sirji
i was wondering why we didn't get TLE , 4^25 >>>>> 10^8(1s), usually we get tle.
I also wondered the same. I believe leetcode test cases for this is not strong enough.
This observation initially made me think of a DP solution, but I couldn't come up with one because maintaining a visited state in an integer value is not possible for a 15x15 matrix. The other option is to take the DP state as dp[r][c][visited[]], which seems like overkill. I wonder if we can solve this in an even more optimized way, perhaps by using a different form of DP
@@adityakurhade1531 making a vector as a state is kinda pointless, coz 99% of the the you will never visit that state ig.
Hi Mik Bhai, please upload Java SOLUTION TOO*
Yes, let me update java after my office hours ❤️
bhaiya apka dsa sheet pls update kardoo bht dino se pending hai
Let me update it this weekend .
Have been very busy with office projects lately ❤️
Ohh i understand bhaiya take ur time and take care of ur health too
can anyone tell me why we have passed address here &dire please tell with example anyone
for (auto &dire : directions) {
cout
isme dp nhi laega kya?
For a given cell [i][j] , we can have different values depending on the cell from where you started your DFS. so you can’t store any past result in a dp array i.e. you can’t memoize or use previous results to solve your current result. Hence you can’t use DP in such cases.
also bro I more doubts yaar ek baat samj nahi aatti recursive call karne ke bhi kayi ways but konsa kab use karna hai and inme farak kya hai x,y are paramters of call and c has result
1st case
c+=fncall(x,y)
c+=fnca(x,y);
c+=fncall(x,y)
c+=fnca();
2nd case we dont use variable rather pass it as paramter
fncall(x,y,c)
fnca(x,y,c);
fncall(x,y,c)
fnca()x,y,c );
dono me fark kya hai how are the values updated in both the cases when rcursive call is made and when backtracking happens bro ye doubt please solve kardo kaafi confuse karta hai also try to cover this in your backtarckig video ki how values are getting updated in variable when recursion and backtrack happesn in both the cases
PLZ REPLY
leetcode has updated the test cases now it is giving tle on same code after 51 test case
It’s passing for me.
Can you share your code ?
class Solution {
public:
int getMaximumGold(vector& grid) {
int m = grid.size();
int n = grid[0].size();
int maxGold = 0;
function dfsBacktrack = [&](int i, int j, int currentGold) {
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) {
return;
}
int goldInCurrentCell = grid[i][j];
currentGold += goldInCurrentCell;
maxGold = max(maxGold, currentGold);
int temp = grid[i][j];
grid[i][j] = 0;
dfsBacktrack(i + 1, j, currentGold);
dfsBacktrack(i - 1, j, currentGold);
dfsBacktrack(i, j + 1, currentGold);
dfsBacktrack(i, j - 1, currentGold);
grid[i][j] = temp;
};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] != 0) {
dfsBacktrack(i, j, 0);
}
}
}
return maxGold;
}
};
// Matrix, Backtracking -- Array
// TC: O(m * n * 4^max(m,n))
// SC: O(m * n)
Moj masti
what is wrong in normal bfs approach??
can somebody explain with this code?
class Solution:
def getMaximumGold(self, grid: List[List[int]]) -> int:
row = len(grid)
col = len(grid[0])
ans = 0
dir = [(1 , 0) , (-1 , 0) ,(0 , 1) , (0 , -1)]
for i in range(row):
for j in range(col):
if grid[i][j]:
s = 0
visited = {(i , j)}
queue = [(i , j , grid[i][j])]
queue = deque(queue)
while queue:
r , c , cost = queue.popleft()
ans = max(ans , cost)
for x in dir:
u = r+x[0]
v = c+x[1]
if 0
Even I want to know that too. Applied similar BFS approach in java
time limit exceeded after 51 test cases
Please share your code.
@@codestorywithMIK class Solution {
public:
int dfs(vector& grid, int i, int j){
int m = grid.size();
int n = grid[0].size();
if(i>=m || i=n || j
@@codestorywithMIK class Solution {
public:
int dfs(vector& grid, int i, int j){
int m = grid.size();
int n = grid[0].size();
if(i>=m || i=n || j
class Solution {
public:
int dfs(vector& grid, int i, int j){
int m = grid.size();
int n = grid[0].size();
if(i>=m || i=n || j
@@codestorywithMIK shared on mail
what is wrong in this code
class Solution {
public:
int dfs(int row, int col, vector &grid, vector &vis, int n, int m)
{
if(grid[row][col] == 0)
return 0;
vis[row][col] = 1;
int sum = grid[row][col];
int a[] = {0, 0, 1, -1};
int b[] = {1, -1, 0, 0};
int val = 0;
for(int i=0;i= 0 && nrow < n && ncol >= 0 && ncol < m && grid[nrow][ncol] != 0 && vis[nrow][ncol] == 0)
{
int a = dfs(nrow, ncol, grid, vis, n, m);
val = max(val, a);
}
}
return sum + val;
}
public:
int getMaximumGold(vector& grid) {
int n = grid.size(), m = grid[0].size();
int ans = 0;
for(int i=0;i
More redable code but TLE why
class Solution {
public:
bool possible(int r, int c, int n, int m) {
if (r >= 0 && r < n && c >= 0 && c < m)
return true;
return false;
}
void dfs(vector& grid, int& ans, int& curr_sum,
vector& visited, int r, int c) {
visited[r][c] = 1;
curr_sum += grid[r][c];
ans = max(ans, curr_sum);
vector dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
for (vector& vec : dir) {
int nr = r + vec[0];
int nc = c + vec[1];
if (possible(nr, nc, grid.size(), grid[0].size()) &&
grid[nr][nc] != 0 && !visited[nr][nc]) {
dfs(grid, ans, curr_sum, visited, nr, nc);
}
}
curr_sum -= grid[r][c];
visited[r][c] = false;
return;
}
int getMaximumGold(vector& grid) {
int ans = 0;
int curr_sum = 0;
int n = grid.size(), m = grid[0].size();
vector visited(n, vector(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j]) {
dfs(grid, ans, curr_sum, visited, i, j);
}
}
}
return ans;
}
plz help me :(
@codestorywithMIK where is the fault in my code ?
class Solution {
public:
int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
bool oom(int i, int j, int row, int col) {
if (i < 0 || i >= row || j < 0 || j >= col)
return true;
return false;
}
int dfs(int sR, int sC, vector& grid, vector& vis, int row, int col) {
if (oom(sR, sC, row, col)) return 0;
vis[sR][sC] = 1;
int gold = grid[sR][sC];
for (int i = 0; i < 4; ++i) {
int nX = sR + dirs[i][0];
int nY = sC + dirs[i][1];
if (oom(nX, nY, row, col) == 0 and grid[nX][nY] != 0 and vis[nX][nY] == -1) {
gold += dfs(nX, nY, grid, vis, row, col);
}
}
return gold;
}
int getMaximumGold(vector& grid) {
int rows = grid.size();
int cols = grid[0].size();
vector vis(rows, vector(cols, -1));
int max_gold = INT_MIN;
for(int i = 0; i < rows; ++i) {
for(int j = 0; j < cols; ++j) {
if (grid[i][j] > 0) {
for (int m = 0; m < rows; ++m)
for(int n = 0; n < cols; ++n)
vis[m][n] = -1;
int temp_gold = dfs(i, j, grid, vis, rows, cols);
max_gold = max(max_gold, temp_gold);
}
}
}
return max_gold;
}
};
I got it...
class Solution {
public:
int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
bool oom(int i, int j, int row, int col) {
if (i < 0 || i >= row || j < 0 || j >= col)
return true;
return false;
}
int dfs(int sR, int sC, vector& grid, vector& vis, int row, int col) {
if (oom(sR, sC, row, col)) return 0;
vis[sR][sC] = 1;
int gold = grid[sR][sC];
int maxx_gold_among_all_dirs = 0;
for (int i = 0; i < 4; ++i) {
int nX = sR + dirs[i][0];
int nY = sC + dirs[i][1];
if (oom(nX, nY, row, col) == 0 and grid[nX][nY] != 0 and vis[nX][nY] == -1) {
maxx_gold_among_all_dirs = max(maxx_gold_among_all_dirs, dfs(nX, nY, grid, vis, row, col));
}
}
vis[sR][sC] = -1;
return gold + maxx_gold_among_all_dirs;
}
int getMaximumGold(vector& grid) {
int rows = grid.size();
int cols = grid[0].size();
vector vis(rows, vector(cols, -1));
int max_gold = 0;
for(int i = 0; i < rows; ++i) {
for(int j = 0; j < cols; ++j) {
if (grid[i][j] > 0) {
for (int m = 0; m < rows; ++m)
for(int n = 0; n < cols; ++n)
vis[m][n] = -1;
int temp_gold = dfs(i, j, grid, vis, rows, cols);
max_gold = max(max_gold, temp_gold);
}
}
}
return max_gold;
}
};
Can you upload shorter videos. Not by skipping important points but by teaching fast.
I mean I understand that slow and long videos usually help to best understand the concept.
Students might have more time but what about working professionals in software industry preparing for interviews to switch jobs ? They might not have 1 hour for understanding a single problem and probably might not even need such an jn depth explanation because they are not beginners. Look at another channel Techdose. He teaches fast and has shorter videos. But his videos are still helpful.
Hi there,
I totally understand your concern and I agree my videos a little lengthy.
Actually the main purpose of this channel was to help beginners because i saw a lot of beginners getting trapped in high paid courses. So it was one of the motivations for starting this.
Being a professional I totally understand that taking out time for DSA is really tough.
May be I can try to create a separate channel where I can teach a little fast which will be mainly for experts or experienced candidates.
Kindly suggest me more ideas on what will be the best solution to this.
Thank you for raising this ❤️❤️❤️
@@codestorywithMIK sir please dont reduce time keep doing whatever you're doing if they want fast they can watch it at 2x or 1.5x
why is it giving WA
class Solution {
public:
int f(int i,int j,vector g){
int n=g.size();
int m= g[0].size();
if(i=m)return 0;
if(i==n-1)return g[i][j];
if(g[i][j]==0)return -1e9;
if(g[i][j]==-1)return 0;
int x=g[i][j];
g[i][j]=-1;
int up=x+f(i-1,j,g);
int down=x+f(i+1,j,g);
int right=x+f(i,j+1,g);
int left= x + f(i,j-1,g);
return max({up,down,left,right});
}
int getMaximumGold(vector& g) {
int n=g.size();
int m= g[0].size();
int ans=0;
for(int i=0;i
here is bfs code but after passing 35,36 test case memory limit exceed
class Solution {
public:
// int DFS(vector& grid,int i , int j){
// int m = grid.size();
// int n = grid[0].size();
// if(i >= m || i= n || j= m || y < 0 || y >= n || grid[x][y] == 0) {
continue;
}
int originalGoldValue = grid[x][y];
grid[x][y] = 0;
int up = bfs(grid, x - 1, y);
int down = bfs(grid, x + 1, y);
int left = bfs(grid, x, y - 1);
int right = bfs(grid, x, y + 1);
grid[x][y] = originalGoldValue;
maxGold = max(maxGold, originalGoldValue + max({up, down, left, right}));
}
return maxGold;
}
int getMaximumGold(vector& grid) {
int m = grid.size();
int n = grid[0].size();
int maxGold = 0;
for(int i =0;i
I solved on my own. Yay 🥹🥹🥹
Me too
Awesome 😇