G-37. Path With Minimum Effort
HTML-код
- Опубликовано: 19 окт 2024
- GfG-Problem Link: bit.ly/3dMBvq6
C++/Java/Codes and Notes Link: takeuforward.o...
DP Series: • Striver's Dynamic Prog...
SDE Sheet: takeuforward.o...
Check out our Website for curated resources:
Our Second Channel: / @striver_79
In case you are thinking to buy courses, please check below:
Code "takeuforward" for 15% off at GFG: practice.geeks...
Code "takeuforward" for 20% off on sys-design: get.interviewr...?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/inv...
Take 750 rs free Amazon Stock from me: indmoney.oneli...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v...
Linkedin/Instagram/Telegram: linktr.ee/take...
---------------------------------------------------------------------------------------------------------------------------
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!
Best feeling when you can solve a problem completely based on the the understanding from previous videos.
AND FROM ONE GOO!!!
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 .
Thanks striver for all videos you have created so far .Learnt a hell lot of things from you .
🙏🙏
GOD LEVEL PLAYLIST ON GRAPHS🙇♀
Supreme quality content, exceptional teaching skills, thanks a lot sir.
I would have a hard time thinking this as a graph problem rather than a DP problem.
BEST BEST BEST TEACHEERRR!!!
It really shows when you are able to solve all these problems by your own!!! THANK YOU BRO!!!
After 3- time watch, i was able to understood it. I got stuck in some cross question, Now happy 😊
Thank you bhaiya ❤
Bhai yaar kya hi samjhaya, ekdum garda . Mazza aa gya
I was able to solve this without watching the video. Thanks to your explanation skills. nice work sir!
MEE TOOO!!! Striver is the BESTTT!!!!
Solved this question without watching video , thanks Striver.
DP came to my mind, as it asked to explore all paths
Understood! Super amazing explanation as always, thank you very much!!
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
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 ❤
Solved it myself. Thanks for training me Striver.
Man what a problem, Thank striver
Thank you striver bhaiya. beautiful explanation .wish to meet you someday
Understood 👍👍 can you please put like this video's eveyday 👍 I will surely watch it👍
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
Solved this question also without any help. With dijkstra. Are these questions really easy or am I improving?
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.
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
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
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.
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
Thanks a lot for the video.
Nice explanation keep on making such videos.
can't we do this with simple BFS?
Amazing sir , bestttttttttt wayyyyyyyy, make that tough question so easyyyyyyy
thank you sir,
🙏🏻🙏🏻❤
Thanks . Learnt a lot from you.
understood, thanks for the great video
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.
understood brother 🤩
thanku striver , it's crystall clear
In cell configuration (1,1) I think the diff should be 7. Please correct me if I am wrong..
Happy teacher's day sir
lol
Thank you sir 😊
This problem can also be solved with binary search on answer + simple BFS.
how?
Great Explanation
so dikastra algo is all about find shortest path to its neighbour and ultimately we get shortest path to destination
dp on trees striver plz
doubt:
why we need to break the loop we can get the answer at the end also by -:
return dist[n-1][m-1]
great explanation👏
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
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?
Why can't we solve this problem using DP?
cause u r gay
Understood Sir, Thank you very much
you know you are genius @striver
did this on my own
should we not use dp in this problem?
Can this be solved using bs?
15:24 I didnot understand this why are we abruptly ending here, instead of waiting till pq becomes empty?
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.
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)
Could this be solved with DP?
Understood! Great explanation..
yo , whats up
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
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
Thanks Striver!!!
understood
Thank you
why we have created absolute diff array[][] when the absolute diff will going to be different in every different path
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.
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.
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 !!!❤❤❤❤❤❤
Thank you bhaiya
Understood Bhaiya
The hiker analogy is terrible for this question...
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
Understand
understood !
understood SIr!
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 ?
nice brother
Understood
Thanks
Understood 👍
He straight away told use dijkstra, but why ? any proof
Understood!
Thank you very much. You are a genius.
this video is good..
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?
Understood✨✨
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?
why is dfs giving tle?
i did this question by taking visited array first and simple queue first ,then i get to know that why solving through simple queue is giving wrong answer i.e..because am exploring every path and for this i am keeping a visited array and it fails at third case when i do dry run on pen and paper,,,but after that i used priority queue and i got my solution accepted...
class Pair{
int first,second,third;
public Pair(int first,int second,int third){
this.first=first;
this.second=second;
this.third=third;
}
}
class Solution {
public int minimumEffortPath(int[][] heights) {
int n=heights.length;
int m=heights[0].length;
int vis[][]=new int[n][m];
PriorityQueue queue=new PriorityQueue((x,y)->x.third-y.third);
queue.add(new Pair(0,0,0));
vis[0][0]=1;
while(!queue.isEmpty()){
int i=queue.peek().first;
int j=queue.peek().second;
int tmax=queue.peek().third;
if(i==n-1 && j==m-1)
return tmax;
queue.remove();
int drow[]={-1,0,1,0};
int dcol[]={0,1,0,-1};
for(int x=0;x=0 && ni=0 && njtmax)
queue.add(new Pair(ni,nj,diff));
else
queue.add(new Pair(ni,nj,tmax));
}
}
}
return -1;
}
}
Done by own.
understood!!
yes
22:27 got heart attack to me at this time 😄
if I use simple DFS with backtrack(of vis array), what will be its TIME COMPLEXITY?
ig 4^n
Understood 😇
Understood 😀
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?
bhaiya sorry i have a doubt in this solution you are returning the ans first time whenever we reach the destination this can lead a wrong ans as you have explain in but not following in code i guess i think we should return the ans after our pq is empty abs will dist[n-1][m-1] i guess can you confirm please
I first commented as not understood but by end of video i edited the comment as understood 😂