G-37. Path With Minimum Effort

[@takeUforward]

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

[@b-techcodewala3030]

best teacher

[@ashishkumaryadav5252]

Outstanding teaching skills.

[@sudhanshushekhar4222]

understood

[@patchasrinivas337]

hi striver, can we solve these problem using dp as like as maximum path sum in a grid

[@rajatraj4297]

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

[@tasneemayham974]

AND FROM ONE GOO!!!

[@highsociety7677]

Watched 4 videos on this question, yours is the only one that made sense! Great teaching, thanks so much!

[@sahilbani7020]

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

[@keertilata20]

GOD LEVEL PLAYLIST ON GRAPHS🙇‍♀

[@codingwithanonymous890]

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

[@satvikdixit]

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]

Wait you guys did dp before graph? Am i doing something wrong f

[@codingwithanonymous890]

@@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

[@techbucks7339]

@@codingwithanonymous890 thanks man i plan to do dp after this .

[@RadhavSharma-mv1jq]

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.

[@rahulkhandelwal7034]

Thanks striver for all videos you have created so far .Learnt a hell lot of things from you . 🙏🙏

[@ashishkumaryadav5252]

Supreme quality content, exceptional teaching skills, thanks a lot sir.

[@tasneemayham974]

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

[@ADI.scussion]

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

[@princenagar1686]

Solved this question without watching video , thanks Striver.

[@Nirala_414]

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

[@nikhil_squats]

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

[@1_______5-j7t]

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

[@tasneemayham974]

MEE TOOO!!! Striver is the BESTTT!!!!

[@PiyushBajaj05]

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?

[@shaikfahim1232]

You can ask him to dry run it using pen and paper having with you and come with this approach

[@cinime]

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

[@vibhorbhatt3076]

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 ❤

[@amalkumar256]

Solved it myself. Thanks for training me Striver.

[@suhelali4547]

Same Question Asked in Goldman Sachs Software Engineer Role.

[@adityanigam8373]

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

[@raghavagrawal9240]

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!

[@akshanshsharma6025]

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

[@simranbandhu9926]

@@akshanshsharma6025 yeah, i too stuck at the same problem. did you find the answer?

[@akshanshsharma6025]

@@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

[@AdityaSharma-pc9cp]

@@akshanshsharma6025 it's the different path we are going through, and in that way, 5 is the max difference, not 6.

[@amalkumar256]

Same I got this one and the last one on my own

[@akshanshsharma6025]

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

[@kamranwarsi12b22]

same doubt

[@037_abhinavkumar3]

same doubt ):

[@muskanagrawal7428]

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.

[@soubhikghosh6564]

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

[@rickk3300]

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.

[@tanujaSangwan]

@@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.

[@rickk3300]

@@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.

[@tanujaSangwan]

@@rickk3300 Right. Thanks for the clarification

[@242deepak]

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?

[@mayuksarkar5077]

Same question

[@guptashashwat]

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]

​@@guptashashwat so is it impossible to return -1? We would get atleast a difference possible?

[@krishnananddubey2870]

@@coderhumai Yes bro there always exist a path from src to dest. You don't need to return -1.

[@zephyr_8]

@@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.

[@iamnoob7593]

Man what a problem, Thank striver

[@pusarlaaishwarya5035]

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

[@lakshya3324]

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

[@coder_boy]

Because of the PriorityQueue, the mindiff is covered so the upcoming diff will be equal to or greater than mindiff. That's why.

[@BruceWayne-mf6ps]

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.

[@paragroy5359]

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

[@vamsikrishnagannamaneni912]

15:24 I didnot understand this why are we abruptly ending here, instead of waiting till pq becomes empty?

[@amanasrani6405]

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

[@unofficialshubham9026]

Thanks . Learnt a lot from you.

[@djpsn7094]

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

[@niteshverma8281]

you know you are genius @striver

[@manohar0742]

Happy teacher's day sir

[@optimus_prime01]

lol

[@rishabhagarwal8049]

Understood Sir, Thank you very much

[@banothutharun2743]

understood brother 🤩

[@tanujaSangwan]

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

[@NavyasriThalluri]

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

[@chandanc7545]

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

[@rushidesai2836]

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.

[@muditkhanna8164]

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 ?

[@Mercer80]

yes

[@Prateek_Mantry]

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

[@FooBar-lb5wf]

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)

[@kaichang8186]

understood, thanks for the great video

[@komalkrishna7836]

Understood! Great explanation..

[@sauravkumardwivedi9384]

yo , whats up

[@Tiyasa-d8f]

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.

[@amitp277]

great explanation👏

[@raghavmanish24]

thanku striver , it's crystall clear

[@meetverma4812]

can't we do this with simple BFS?

[@shivamgupta3520]

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

[@rishabhgupta9846]

that is syntax for min priority queue ,we need to take pair as data type for PQ

[@amansinghal4663]

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'

[@shivamgupta3520]

@@amansinghal4663Thanks I have learnt the heap now that time i don't know about the heap DS.

[@amansingh.h716]

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

[@shaddyrogue9430]

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

[@swapnilhajare5557]

Same issue

[@SatyamEdits]

yesss......

[@nishantsah6981]

This Problem is also on Leetcode Problem 1631

[@tejasc7409]

@@nishantsah6981 No It works fine in Leetcode

[@abhishek__anand__]

Great Explanation

[@yaswanthtogarapu8458]

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

[@mrlord8519]

Same doubt bro....any lead now

[@tasneemayham974]

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?

[@Prateek_Mantry]

@@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}} ?

[@tasneemayham974]

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

[@anubhavpabby6856]

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?

[@anubhavpabby6856]

Bhaiya I am geting confused like why we cannot use dfs or dp here to calculate the minimum answer.

[@takeUforward]

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

[@SatyamEdits]

@@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......

[@krishanpratap3286]

@@SatyamEdits instead of just simple recursion agar dp use kare toh work kar jayega shayd

[@b28venkatasivakalyankaliki81]

@boomsi69 Thank you for the explanation !!!❤❤❤❤❤❤

[@amansinghal4663]

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

[@puspendrayadav8931]

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

[@deviprasad_bal]

how?

[@nownow1025]

bro tell us

[@adebisisheriff159]

Thanks Striver!!!

[@Sakuna172]

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

[@UECAshutoshKumar]

Thank you sir 😊

[@nehatanganiya5491]

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

[@udaykumarpg3874]

Why can't we solve this problem using DP?

[@somsk56]

cause u r gay

[@jayantgahlot2653]

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

[@ayushranjan1265]

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

[@subhashpatel5861]

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

[@parthmadan671]

how

[@mrlord8519]

Dp ok but how on binary search on answers?

[@ithcaironsthlotron5546]

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

[@yashbankar4207]

ig 4^n

[@amansingh.h716]

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

[@mriduljain6809]

Understood Bhaiya

[@abhishekranjan8741]

dp on trees striver plz

[@development5298]

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 ?

[@alexwhitewood6480]

The hiker analogy is terrible for this question...

[@OnstreamGaming]

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

[@adityasaxena6971]

Understood✨✨

[@CodeMode9313]

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

[@optimus_prime01]

do a dry run

[@aniketlal1657]

Could this be solved with DP?

[@-VLaharika]

Understood 👍

[@mmbmmbmmb]

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

[@tasneemayham974]

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?

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@Dishant-nn7uk]

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

[@AyushSharma-ux4fk]

should we not use dp in this problem?

[@souravjoshi2293]

22:42 confusing here

[@siddharthmishra8233]

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

[@Mohit_Q]

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

[@The_Shubham_Soni]

UNDERSTOOD.

[@parshchoradia9909]

understood SIr!

[@priyanshvatsal9791]

Understood 😇

[@gamerglobe4839]

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...

[@amansinghal4663]

yes i have the same doubt, by doing this, i was getting wrong answer in previous question for some test cases and getting TLE in this question for all the test cases.

[@gamerglobe4839]

@@amansinghal4663 bro since we are learning to apply dijkstra that's why he used distance array and also in some questions without distance array ,finding answer could be a complicating stuff.

[@amansinghal4663]

​@@gamerglobe4839 I see....

[@aadilkhan4867]

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

[@gamerglobe4839]

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

[@TarunKumar-cn6in]

Understood 😀

[@dank7044]

did this on my own

[@anshumanbehera3706]

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

[@Learnprogramming-q7f]

Thank you bhaiya

[@girikgarg8]

Can we return dist[n-1][n-1] in the main function, instead of returning from the while loop in the priority queue

[@deviprasad_bal]

yes you can do it

[@aryanbarnwal5645]

why is dfs giving tle?

[@dhawalpatil7779]

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

[@krisify]

Can this be solved using bs?

[@justanuhere]

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

[@tasneemayham974]

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?

[@nownow1025]

@@tasneemayham974 thanks

[@muskangupta5873]

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}}); }

[@ankitanand1046]

Thank you

[@p38_amankuldeep75]

understood🧡❤🧡