Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞 Do follow me on Instagram: striver_79
Whenever there is an optimisation problem, i.e finding maximum or minimum. You generally have 3 options. DP ,Greedy , Binary search. Djiktra is kind of a Greedy+DP thing where the states of dp ( or nodes in the graph) can have greedy transitions. That is how I think. Very similar to you
@@techbucks7339 theres not any specific order bro , like recursion is used in both dp and graph traversals so recursion is pre requisite other things you can cover in the series
One thing that helped me to understand the algorithm was to consider the distance array as effort array, at each element, if the currentEffort is greater than the max(absolute diff, effortToReachPreviousElement), then update its effort to max(absolute diff, effortToReachPreviousElement) and move forward.
Hi Striver, One basic question: We can brainstorm such questions or solve if we draw such graph like matrix and queue with pen and paper or using digital pen in the draw tool. But how to solve the same in google doc or any notepad, because in the real interview we have to solve in that?
I can't believe the level of simplicity you follow to teach us these complex topics with ease. I can never imagine understanding this stuff with minimal efforts without Striver bhaiya ❤
why are you returning diff when top element in priority queue has row and col as n-1? what if all the paths reaching that cell have not been traversed yet?
Let me explain: You can also do without early returning ie at the end simply dist[n-1][m-1]. Priority queue/set gives smallest value on top, if that smallest value is destination then that has to be the ans because, you cannot further reduce the value by using other bigger values present in the DS.
@@coderhumai for this question, you can. actually, there always exists certain paths from (0,0) to (row-1,col-1), so your return will always occur in the queue.
Hi Striver there is a lot of concern in many questions on some questions on grids cant be solved by using dp? please give a general explanation over that. many are stuck on this problem including me
We can use DP to solve only those problems which can be decomposed into such smaller subproblems which are not dependent on each other, like if there is a subproblem A and a subproblem B of the main problem, then if A depends on the result of B, then B should not depend on the result of A and vice versa, that is, the unidirectional dependency among subproblems should be maintained. But here, in this problem, if you look carefully, two subproblems depend on each other, hence we cannot apply dp here.
@@rickk3300 Movement Restriction (Right and Down): DP works effectively because you can break down the problem into simpler subproblems where each subproblem (cell) only depends on a fixed set of previous subproblems (the cells directly above or to the left). The problem structure is simple and doesn’t involve revisiting cells or complex path updates. Movement in All Directions: DP is less straightforward due to the possibility of revisiting cells and the need to handle complex dependencies between different paths. Algorithms designed for shortest path problems in graphs (like Dijkstra’s or A*) are better suited to handle these cases, as they are designed to efficiently manage dynamic path updates and complex dependencies.
Awesme explaination since the first video. Was able to solve past question and this question without watching the explaination! Big win win for me. Thanks a lot!
at the time stamp 12:54 I didn't get it when the previous difference is 6 and the new difference is 5 then why we update it because initially we take the maximum of the difference
at the time stamp 12:54 I didn't get it when the previous difference is 6 and the new difference is 5 then why we update it because initially we take the maximum of the difference
we update effort with maximum and dis array with minimum, earlier we updated dis[0][2] with 1 and not 0 because effort is max(0,1)=1 and updatd dis with min(effort, 1e9)=1, similarly we updated dis[1][1] with min(effort(viz 5),dis[1][1](viz 6)) = 5.
Can this also be thought of like the Painter's partition problem using Binary search? The maximum effort can be the sum of differences and minimum is 0. I thought about it because here we need to find MINIMUM OF THE MAXIMUM effort, just like in the painter's partition problem.
So the main point to remember other than dijktra is when looking for nodes in all 4 directions if we found a node which is row=n-1 and col=n-1 we just push it into the pq and we declare the answer only when the top element of pq is the node at row=n-1 and col=n-1 then only we declare the answer ?
Hi guys, have a small doubt that dijkstra's algorithm seems to use the same key idea from what dynamic programming does (don't think for the overlapping sub problems rather the key idea of optimization i'm saying) , because every time it optimizes the vertex locally but from all possible directions, ?
Yes, it does. The nice thing in Dijkstra is that it relies on Greedy more than on exploring all paths. Like in DP, you don't care about which one comes first. You are choosing randomly, but in Dijkstra we are first prioritizing the least distances and once we reach our destination we have the answer. Meanwhile DP, cannot do that. Even if you reach the final destination, since you are moving randomly, there might be a path that is yet to be discovered. When you say it optimizes vertices locally, yes both optimize locally, but the difference is in the process. In DP, we explore the entire path to the end of the base case / destination, and THEN return and explore the next path and optimize the vertex. In Dijkstra, WHILE we are exploring the path, we instantly choose "I am the lesser vertex. Why are you here?" So the vertex is optimized. So when we reach the end we have the answer. I hope I made it clear. Is there anything vague?
@@tasneemayham974 In this question why we are stopping at {2, {2, 2}} ? In future operations we might have found a lesser difference path like {1, {2,2}} ?
@@Prateek_Mantry Impossible. If we are using a PQ that ensures the elements are sorted according to least distance. Then we are certain, that when we reach {2, {2,2}} there is NO way a lesser path could've been found. Because if there was a path indeed it would've been popped before {2,{2,2}}. Got me?
because in the previous lines he will remove the node that has least distance and so when u remove prom that priorityQueue only the node with least distance will be picked and if that node is at last index then u found best path already, that is what i feel
see the c++ STL video of striver, jump to the priority queue part, there you will see that for MAX HEAP priority queue, the syntax is simple, but for MIN HEAP, the syntax is larger and different. So in that syntax, just replace ''int'' from everywhere with pair because in this question, the data type we want to store in the priority queue is not simple 'int', it's a 'pair'
First i try bruteforce approach normal BFS go to all direction --GETS TLE Dikastra algo goes in 4 direction which ever is small it goes there and generate shortest path
The greedy approach of selecting the element with the minimum dist value from the priority queue (that is selecting the unvisited node which is closest to the source) ensures that by the time a node 'u' is extracted from the priority queue, dist[u] is already set to the shortest path distance from the source. This is a property of Dijkstra's algorithm (independent of this problem)
Striver bhiaya can we also use the concept of dynamic programming to calculate minimum effort? BTW I am getting confused like when to apply dp and when to use dijsktra to calculate min effort?
You can try, I always say to write code and submit. And then see which test cass it is failing. Then write the test case, in most of the cases you get to know why
@@anubhavpabby6856 with dfs you will get correct answer but it will fail the time limit.... because you may have to visit some nodes alot of times.....(same problem arises with using Queue also..instead of priority queue)...... Before learning a new algorithm try to find out what are the problems you are facing with your current knowledge of algorithm....attempt the question with your knowledge...then find out the problems you faced...and then finally see how striver bhaiya has solved those problems with new algorithm......
I think this question can be solved without the distance matrix also, i tried it using priority queue without distance matrix but it's giving TLE. I defined the priority queue as pair of 2 pairs. Like this: {{a,b},{c,d}} where, a = absolute difference b = current value in the given matrix c = row d = column
Because we are taking the priorityQueue which takes least distances. So, every other distance is greater than what I currently have. And since this is the last node, so there is no chance of different paths. It's over. Greedy on the last node works. Get me?
class Solution { public int minimumEffortPath(int[][] heights) { int n = heights.length; int m = heights[0].length; PriorityQueue pq = new PriorityQueue(Comparator.comparingInt(t -> t.d)); int[][] dist = new int[n][m]; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ dist[i][j] = (int)(1e9); } } dist[0][0] = 0; pq.add(new Tuple(0,0,0)); int[] delRow = {-1,0,1,0}; int[] delCol = {0,1,0,-1}; while(pq.isEmpty() == false){ Tuple t = pq.poll(); int distance = t.d; int row = t.row; int col = t.col; for(int i = 0; i < 4; i++){ int nRow = row + delRow[i]; int nCol = col + delCol[i];
if(nRow >= 0 && nRow < n && nCol >= 0 && nCol < m){ int newEffort = Math.max(distance, Math.abs(heights[row][col] - heights[nRow][nCol])); if(newEffort < dist[nRow][nCol]){ dist[nRow][nCol] = newEffort; pq.add(new Tuple(newEffort,nRow,nCol)); } } } } return dist[n-1][m-1]; } } Return statement should be at the end, not while taking out of PriorityQueue. Tested on LeetCode.
Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞
Do follow me on Instagram: striver_79
best teacher
Outstanding teaching skills.
understood
hi striver, can we solve these problem using dp as like as maximum path sum in a grid
Watched 4 videos on this question, yours is the only one that made sense! Great teaching, thanks so much!
i always try this approach fitting algorithms if its asked minimum think of binary search, dijkstra algorithm or dp
Whenever there is an optimisation problem, i.e finding maximum or minimum. You generally have 3 options. DP ,Greedy , Binary search. Djiktra is kind of a Greedy+DP thing where the states of dp ( or nodes in the graph) can have greedy transitions. That is how I think. Very similar to you
Wait you guys did dp before graph? Am i doing something wrong f
@@techbucks7339 theres not any specific order bro , like recursion is used in both dp and graph traversals so recursion is pre requisite other things you can cover in the series
@@codingwithanonymous890 thanks man i plan to do dp after this .
Best feeling when you can solve a problem completely based on the the understanding from previous videos.
AND FROM ONE GOO!!!
I would have a hard time thinking this as a graph problem rather than a DP problem.
GOD LEVEL PLAYLIST ON GRAPHS🙇♀
Thanks striver for all videos you have created so far .Learnt a hell lot of things from you .
🙏🙏
Supreme quality content, exceptional teaching skills, thanks a lot sir.
BEST BEST BEST TEACHEERRR!!!
It really shows when you are able to solve all these problems by your own!!! THANK YOU BRO!!!
DP came to my mind, as it asked to explore all paths
Bhai yaar kya hi samjhaya, ekdum garda . Mazza aa gya
After 3- time watch, i was able to understood it. I got stuck in some cross question, Now happy 😊
Thank you bhaiya ❤
One thing that helped me to understand the algorithm was to consider the distance array as effort array, at each element, if the currentEffort is greater than the max(absolute diff, effortToReachPreviousElement), then update its effort to max(absolute diff, effortToReachPreviousElement) and move forward.
Solved this question without watching video , thanks Striver.
I was able to solve this without watching the video. Thanks to your explanation skills. nice work sir!
MEE TOOO!!! Striver is the BESTTT!!!!
Hi Striver,
One basic question: We can brainstorm such questions or solve if we draw such graph like matrix and queue with pen and paper or using digital pen in the draw tool. But how to solve the same in google doc or any notepad, because in the real interview we have to solve in that?
You can ask him to dry run it using pen and paper having with you and come with this approach
Understood! Super amazing explanation as always, thank you very much!!
I can't believe the level of simplicity you follow to teach us these complex topics with ease.
I can never imagine understanding this stuff with minimal efforts without Striver bhaiya ❤
why are you returning diff when top element in priority queue has row and col as n-1? what if all the paths reaching that cell have not been traversed yet?
Same question
Let me explain: You can also do without early returning ie at the end simply dist[n-1][m-1]. Priority queue/set gives smallest value on top, if that smallest value is destination then that has to be the ans because, you cannot further reduce the value by using other bigger values present in the DS.
@@guptashashwat so is it impossible to return -1? We would get atleast a difference possible?
@@coderhumai Yes bro there always exist a path from src to dest. You don't need to return -1.
@@coderhumai for this question, you can. actually, there always exists certain paths from (0,0) to (row-1,col-1), so your return will always occur in the queue.
Solved it myself. Thanks for training me Striver.
Same Question Asked in Goldman Sachs Software Engineer Role.
Hi Striver there is a lot of concern in many questions on some questions on grids cant be solved by using dp? please give a general explanation over that. many are stuck on this problem including me
We can use DP to solve only those problems which can be decomposed into such smaller subproblems which are not dependent on each other, like if there is a subproblem A and a subproblem B of the main problem, then if A depends on the result of B, then B should not depend on the result of A and vice versa, that is, the unidirectional dependency among subproblems should be maintained. But here, in this problem, if you look carefully, two subproblems depend on each other, hence we cannot apply dp here.
@@rickk3300
Movement Restriction (Right and Down):
DP works effectively because you can break down the problem into simpler subproblems where each subproblem (cell) only depends on a fixed set of previous subproblems (the cells directly above or to the left).
The problem structure is simple and doesn’t involve revisiting cells or complex path updates.
Movement in All Directions:
DP is less straightforward due to the possibility of revisiting cells and the need to handle complex dependencies between different paths.
Algorithms designed for shortest path problems in graphs (like Dijkstra’s or A*) are better suited to handle these cases, as they are designed to efficiently manage dynamic path updates and complex dependencies.
@@tanujaSangwan exactly, that's what I said! If there is a need to revisit cells or there are complex dependencies, we can never apply dp.
@@rickk3300 Right. Thanks for the clarification
Awesme explaination since the first video. Was able to solve past question and this question without watching the explaination! Big win win for me. Thanks a lot!
at the time stamp 12:54 I didn't get it when the previous difference is 6 and the new difference is 5 then why we update it because initially we take the maximum of the difference
@@akshanshsharma6025 yeah, i too stuck at the same problem. did you find the answer?
@@simranbandhu9926 not till now but if I find the answer I will let you know bro but if you find then please tell me too
@@akshanshsharma6025 it's the different path we are going through, and in that way, 5 is the max difference, not 6.
Same I got this one and the last one on my own
Understood 👍👍 can you please put like this video's eveyday 👍 I will surely watch it👍
at the time stamp 12:54 I didn't get it when the previous difference is 6 and the new difference is 5 then why we update it because initially we take the maximum of the difference
same doubt
same doubt ):
we update effort with maximum and dis array with minimum, earlier we updated dis[0][2] with 1 and not 0 because effort is max(0,1)=1 and updatd dis with min(effort, 1e9)=1, similarly we updated dis[1][1] with min(effort(viz 5),dis[1][1](viz 6)) = 5.
Thank you striver bhaiya. beautiful explanation .wish to meet you someday
Man what a problem, Thank striver
Im not able to understand the loop break condition ( why we will not find a better solution in future) at 15:10
Because of the PriorityQueue, the mindiff is covered so the upcoming diff will be equal to or greater than mindiff. That's why.
15:24 I didnot understand this why are we abruptly ending here, instead of waiting till pq becomes empty?
Amazing sir , bestttttttttt wayyyyyyyy, make that tough question so easyyyyyyy
thank you sir,
🙏🏻🙏🏻❤
Can this also be thought of like the Painter's partition problem using Binary search? The maximum effort can be the sum of differences and minimum is 0. I thought about it because here we need to find MINIMUM OF THE MAXIMUM effort, just like in the painter's partition problem.
Thanks a lot for the video.
Nice explanation keep on making such videos.
understood brother 🤩
Thanks . Learnt a lot from you.
22:27 got heart attack to me at this time 😄
So the main point to remember other than dijktra is when looking for nodes in all 4 directions if we found a node which is row=n-1 and col=n-1 we just push it into the pq and we declare the answer only when the top element of pq is the node at row=n-1 and col=n-1 then only we declare the answer ?
yes
16:28 do not conclude, it should have been better if you have simulated more until all the elements are empty. However, I loved your video.
Thank you sir 😊
understood, thanks for the great video
you know you are genius @striver
Understood Sir, Thank you very much
thanku striver , it's crystall clear
Thanks Striver!!!
Hi guys, have a small doubt that dijkstra's algorithm seems to use the same key idea from what dynamic programming does (don't think for the overlapping sub problems rather the key idea of optimization i'm saying) , because every time it optimizes the vertex locally but from all possible directions, ?
Same doubt bro....any lead now
Yes, it does. The nice thing in Dijkstra is that it relies on Greedy more than on exploring all paths. Like in DP, you don't care about which one comes first. You are choosing randomly, but in Dijkstra we are first prioritizing the least distances and once we reach our destination we have the answer. Meanwhile DP, cannot do that. Even if you reach the final destination, since you are moving randomly, there might be a path that is yet to be discovered.
When you say it optimizes vertices locally, yes both optimize locally, but the difference is in the process. In DP, we explore the entire path to the end of the base case / destination, and THEN return and explore the next path and optimize the vertex. In Dijkstra, WHILE we are exploring the path, we instantly choose "I am the lesser vertex. Why are you here?" So the vertex is optimized. So when we reach the end we have the answer.
I hope I made it clear. Is there anything vague?
@@tasneemayham974 In this question why we are stopping at {2, {2, 2}} ? In future operations we might have found a lesser difference path like {1, {2,2}} ?
@@Prateek_Mantry Impossible. If we are using a PQ that ensures the elements are sorted according to least distance. Then we are certain, that when we reach {2, {2,2}} there is NO way a lesser path could've been found. Because if there was a path indeed it would've been popped before {2,{2,2}}. Got me?
Great Explanation
can't we do this with simple BFS?
why we returning the answer value early , instead of queue becoming empty and returning dist[m-1][n-1] where m=no. of rows and n= no. of cols
because in the previous lines he will remove the node that has least distance and so when u remove prom that priorityQueue only the node with least distance will be picked and if that node is at last index then u found best path already, that is what i feel
can u please explain the line of priority queue how u write this in this question and also
in dijkstra algorithm i didn,t understand it
that is syntax for min priority queue ,we need to take pair as data type for PQ
see the c++ STL video of striver, jump to the priority queue part,
there you will see that for MAX HEAP priority queue, the syntax is simple, but for MIN HEAP, the syntax is larger and different.
So in that syntax, just replace ''int'' from everywhere with pair because in this question, the data type we want to store in the priority queue is not simple 'int', it's a 'pair'
@@amansinghal4663Thanks I have learnt the heap now that time i don't know about the heap DS.
Understood! Great explanation..
yo , whats up
First i try bruteforce approach normal BFS go to all direction --GETS TLE
Dikastra algo goes in 4 direction which ever is small it goes there and generate shortest path
great explanation👏
Why are we stopping at {2, {2, 2}} ? In future operations we might have found a lesser difference path like {1, {2,2}} ?
The greedy approach of selecting the element with the minimum dist value from the priority queue (that is selecting the unvisited node which is closest to the source) ensures that by the time a node 'u' is extracted from the priority queue, dist[u] is already set to the shortest path distance from the source. This is a property of Dijkstra's algorithm (independent of this problem)
Happy teacher's day sir
lol
This problem can also be solved with binary search on answer + simple BFS.
how?
bro tell us
Understood Bhaiya
Understood✨✨
Solved this question also without any help. With dijkstra. Are these questions really easy or am I improving?
There is similar issue with this question as well.
Your Code's output is:
30080
It's Correct output is:
30080
Output Difference
30080
Same issue
yesss......
This Problem is also on Leetcode Problem 1631
@@nishantsah6981 No It works fine in Leetcode
Striver bhiaya can we also use the concept of dynamic programming to calculate minimum effort? BTW I am getting confused like when to apply dp and when to use dijsktra to calculate min effort?
Bhaiya I am geting confused like why we cannot use dfs or dp here to calculate the minimum answer.
You can try, I always say to write code and submit. And then see which test cass it is failing. Then write the test case, in most of the cases you get to know why
@@anubhavpabby6856 with dfs you will get correct answer but it will fail the time limit.... because you may have to visit some nodes alot of times.....(same problem arises with using Queue also..instead of priority queue)......
Before learning a new algorithm try to find out what are the problems you are facing with your current knowledge of algorithm....attempt the question with your knowledge...then find out the problems you faced...and then finally see how striver bhaiya has solved those problems with new algorithm......
@@SatyamEdits instead of just simple recursion agar dp use kare toh work kar jayega shayd
@boomsi69 Thank you for the explanation !!!❤❤❤❤❤❤
In cell configuration (1,1) I think the diff should be 7. Please correct me if I am wrong..
Understood 👍
if I use simple DFS with backtrack(of vis array), what will be its TIME COMPLEXITY?
ig 4^n
I think this question can be solved without the distance matrix also, i tried it using priority queue without distance matrix but it's giving TLE. I defined the priority queue as pair of 2 pairs.
Like this:
{{a,b},{c,d}}
where,
a = absolute difference
b = current value in the given matrix
c = row
d = column
Thank you bhaiya
this question can be done using dp as well as binary search on answers too :)
how
Dp ok but how on binary search on answers?
How we get this types of approaches... I can't imagine this approach... I don't know why...I know this can solved using bfs but
Thank you
UNDERSTOOD.
Why can't we solve this problem using DP?
cause u r gay
understood SIr!
Understood 😇
dp on trees striver plz
Understood 😀
understood !
doubt:
why we need to break the loop we can get the answer at the end also by -:
return dist[n-1][m-1]
understood🧡❤🧡
did this on my own
this video is good..
can someone pls explain why {2,{2,2}} will be final answer and there wouldnt be any lesser distnce
Because we are taking the priorityQueue which takes least distances. So, every other distance is greater than what I currently have. And since this is the last node, so there is no chance of different paths. It's over. Greedy on the last node works. Get me?
Understood!
why will a normal bfs not work for this ? i have written the same code but its just for bfs why doesnt this work then ?
Could this be solved with DP?
Thank you very much. You are a genius.
I first commented as not understood but by end of video i edited the comment as understood 😂
understood!!
class Solution {
public int minimumEffortPath(int[][] heights) {
int n = heights.length;
int m = heights[0].length;
PriorityQueue pq = new PriorityQueue(Comparator.comparingInt(t -> t.d));
int[][] dist = new int[n][m];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
dist[i][j] = (int)(1e9);
}
}
dist[0][0] = 0;
pq.add(new Tuple(0,0,0));
int[] delRow = {-1,0,1,0};
int[] delCol = {0,1,0,-1};
while(pq.isEmpty() == false){
Tuple t = pq.poll();
int distance = t.d;
int row = t.row;
int col = t.col;
for(int i = 0; i < 4; i++){
int nRow = row + delRow[i];
int nCol = col + delCol[i];
if(nRow >= 0 && nRow < n && nCol >= 0 && nCol < m){
int newEffort = Math.max(distance, Math.abs(heights[row][col] - heights[nRow][nCol]));
if(newEffort < dist[nRow][nCol]){
dist[nRow][nCol] = newEffort;
pq.add(new Tuple(newEffort,nRow,nCol));
}
}
}
}
return dist[n-1][m-1];
}
}
Return statement should be at the end, not while taking out of PriorityQueue. Tested on LeetCode.
Understand
Thanks
should we not use dp in this problem?
Can we return dist[n-1][n-1] in the main function, instead of returning from the while loop in the priority queue
yes you can do it
why is dfs giving tle?
Understood!!!
i have a confusion we got the destination at with effort of 3 already so why didn't it returned 3?
bcoz we are prioriy queue (min heap) , to uski call he nahi hogi and us se phela fir {2,{2,2}} call hogi and we will get the answer
so dikastra algo is all about find shortest path to its neighbour and ultimately we get shortest path to destination
nice brother
Can this be solved using bs?
efficient c++ code:
int n=heights.size();
int m=heights[0].size();
priority_queue q;
q.push({0,{0,0}});
vector dist(n,vector (m,1e9));
dist[0][0]=0;
while(!q.empty()){
int dis=q.top().first;
int row=q.top().second.first;
int col=q.top().second.second;
q.pop();
for(int k=-1;k=0 && row+kmax(dis,abs(heights[row][col]-heights[row+k][col]))){
dist[row+k][col]=max(dis,abs(heights[row][col]-heights[row+k][col]));
q.push({dist[row+k][col],{row+k,col}});
}
}
if(col+k>=0 && col+kmax(dis,abs(heights[row][col]-heights[row][col+k]))){
dist[row][col+k]=max(dis,abs(heights[row][col]-heights[row][col+k]));
q.push({dist[row][col+k],{row,col+k}});
}
}
}
}
return dist[n-1][m-1];
what is the point of using distance array here? i tried doing this without a distance array it gives tle why?
Because won't you go back and forth? In your code ask yourself what prevents my algorithm from going back to the cell it came from?
@@tasneemayham974 thanks
Understood