G-37. Path With Minimum Effort 

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

i always try this approach fitting algorithms if its asked minimum think of binary search, dijkstra algorithm or dp

I would have a hard time thinking this as a graph problem rather than a DP problem.

The hiker analogy is terrible for this question...

Watched 4 videos on this question, yours is the only one that made sense! Great teaching, thanks so 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?

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?

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.

GOD LEVEL PLAYLIST ON GRAPHS🙇‍♀

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

Solved this question also without any help. With dijkstra. Are these questions really easy or am I improving?

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

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.

After 3- time watch, i was able to understood it. I got stuck in some cross question, Now happy 😊 Thank you bhaiya ❤

Best feeling when you can solve a problem completely based on the the understanding from previous videos.

Why can't we solve this problem using DP?

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

can't we do this with simple BFS?

BEST BEST BEST TEACHEERRR!!! It really shows when you are able to solve all these problems by your own!!! THANK YOU BRO!!!

Why are we stopping at {2, {2, 2}} ? In future operations we might have found a lesser difference path like {1, {2,2}} ?

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

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.

why writing condition like this gives TLE if(nrow >= 0 && nrow < rows && ncol >= 0 && ncol < columns && abs(heights[nrow][ncol] - heights[x][y]) < ans[nrow][ncol]) { int new_diff = max(diff, abs(heights[nrow][ncol] - heights[x][y])); ans[nrow][ncol] = new_diff; q.push({new_diff, {nrow, ncol}}); }

why we have created absolute diff array[][] when the absolute diff will going to be different in every different path

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

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

He straight away told use dijkstra, but why ? any proof

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 ?

DP came to my mind, as it asked to explore all paths

so dikastra algo is all about find shortest path to its neighbour and ultimately we get shortest path to destination

understood brother 🤩

Im not able to understand the loop break condition ( why we will not find a better solution in future) at 15:10

can someone pls explain why {2,{2,2}} will be final answer and there wouldnt be any lesser distnce

Man what a problem, Thank striver

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?

I was able to solve this without watching the video. Thanks to your explanation skills. nice work sir!

Understood! Super amazing explanation as always, thank you very much!!

can we do this instead of dr and dc for(int i=-1;i

This problem can also be solved with binary search on answer + simple BFS.

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 ?

Thank you striver bhaiya. beautiful explanation .wish to meet you someday

22:27 got heart attack to me at this time 😄

Understood 👍👍 can you please put like this video's eveyday 👍 I will surely watch it👍

understood, thanks for the great video

In cell configuration (1,1) I think the diff should be 7. Please correct me if I am wrong..

doubt: why we need to break the loop we can get the answer at the end also by -: return dist[n-1][m-1]

if I use simple DFS with backtrack(of vis array), what will be its TIME COMPLEXITY?

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, ?

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

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.

what is the point of using distance array here? i tried doing this without a distance array it gives tle why?

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 ❤

Can this be solved using bs?

understood

You didnt create a min heap in code

dp on trees striver plz

Amazing sir , bestttttttttt wayyyyyyyy, make that tough question so easyyyyyyy thank you sir, 🙏🏻🙏🏻❤

There is similar issue with this question as well. Your Code's output is: 30080 It's Correct output is: 30080 Output Difference 30080

Solved this question without watching video , thanks Striver.

you w8 might find someone better...:)

why we are using distance array here even without this,we can solve this and previous problem too by just using priority queue min heap because it always pops up min value and we proceed with it and at the end of the day we can return our answer...

understood

Understood

understood !

Thank you sir 😊

nice brother

I first commented as not understood but by end of video i edited the comment as understood 😂

Understood

understood

Understood

Bhai yaar kya hi samjhaya, ekdum garda . Mazza aa gya

understood

Understood

Understood

US

Could this be solved with DP?

understood

Understood

thanku striver , it's crystall clear

understood

understood

Understood

Understood

Thanks a lot for the video. Nice explanation keep on making such videos.

i got time limited exceed in thr case of java code so can you plz optimized the code of java I am not able to submit the solution in gfg

habibi video me bas ye clear nhi ho rha ki jab 2 destination cell me store hua then usske baad hi kyu return kardia answer why didnt we explore the remaining iteration of the queues

should we not use dp in this problem?

this is one of confucious problems

this question can be done using dp as well as binary search on answers too :)

🎉

i have a confusion we got the destination at with effort of 3 already so why didn't it returned 3?

why is dfs giving tle?

did this on my own

22:42 confusing here

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

Understood

Understood

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];

Understood Sir, Thank you very much