G-37. Path With Minimum Effort

Поділитися
Вставка
  • Опубліковано 22 гру 2024

КОМЕНТАРІ •

  • @takeUforward
    @takeUforward  2 роки тому +51

    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

  • @highsociety7677
    @highsociety7677 2 роки тому +23

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

  • @codingwithanonymous890
    @codingwithanonymous890 2 роки тому +64

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

    • @satvikdixit
      @satvikdixit 2 роки тому +46

      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
      @techbucks7339 Рік тому

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

    • @codingwithanonymous890
      @codingwithanonymous890 Рік тому +2

      @@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
      @techbucks7339 Рік тому +1

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

  • @rajatraj4297
    @rajatraj4297 Рік тому +9

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

  • @sahilbani7020
    @sahilbani7020 3 місяці тому +19

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

  • @keertilata20
    @keertilata20 2 роки тому +17

    GOD LEVEL PLAYLIST ON GRAPHS🙇‍♀

  • @rahulkhandelwal7034
    @rahulkhandelwal7034 2 роки тому +20

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

  • @ashishkumaryadav5252
    @ashishkumaryadav5252 2 роки тому +13

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

  • @tasneemayham974
    @tasneemayham974 7 місяців тому +2

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

  • @nikhil_squats
    @nikhil_squats 4 місяці тому +4

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

  • @ADI.scussion
    @ADI.scussion Рік тому +2

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

  • @Nirala_414
    @Nirala_414 Рік тому +14

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

  • @RadhavSharma-mv1jq
    @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.

  • @princenagar1686
    @princenagar1686 5 місяців тому +1

    Solved this question without watching video , thanks Striver.

  • @1_______5-j7t
    @1_______5-j7t 8 місяців тому +1

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

    • @tasneemayham974
      @tasneemayham974 7 місяців тому

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

  • @PiyushBajaj05
    @PiyushBajaj05 2 роки тому +14

    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
      @shaikfahim1232 2 роки тому +1

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

  • @cinime
    @cinime 2 роки тому +2

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

  • @vibhorbhatt3076
    @vibhorbhatt3076 7 місяців тому

    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 ❤

  • @242deepak
    @242deepak Рік тому +12

    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
      @mayuksarkar5077 Рік тому

      Same question

    • @guptashashwat
      @guptashashwat Рік тому +9

      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
      @coderhumai Рік тому

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

    • @krishnananddubey2870
      @krishnananddubey2870 Рік тому +1

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

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

  • @amalkumar256
    @amalkumar256 Рік тому +2

    Solved it myself. Thanks for training me Striver.

  • @suhelali4547
    @suhelali4547 27 днів тому +1

    Same Question Asked in Goldman Sachs Software Engineer Role.

  • @soubhikghosh6564
    @soubhikghosh6564 2 роки тому +12

    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
      @rickk3300 Рік тому +13

      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
      @tanujaSangwan 3 місяці тому +3

      @@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
      @rickk3300 3 місяці тому +1

      @@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
      @tanujaSangwan 3 місяці тому +1

      @@rickk3300 Right. Thanks for the clarification

  • @raghavagrawal9240
    @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
      @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
      @simranbandhu9926 Рік тому

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

    • @akshanshsharma6025
      @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
      @AdityaSharma-pc9cp Рік тому

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

    • @amalkumar256
      @amalkumar256 Рік тому

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

  • @pusarlaaishwarya5035
    @pusarlaaishwarya5035 2 роки тому +1

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

  • @akshanshsharma6025
    @akshanshsharma6025 Рік тому +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

    • @kamranwarsi12b22
      @kamranwarsi12b22 Рік тому

      same doubt

    • @037_abhinavkumar3
      @037_abhinavkumar3 10 місяців тому

      same doubt ):

    • @muskanagrawal7428
      @muskanagrawal7428 5 місяців тому

      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.

  • @adityanigam8373
    @adityanigam8373 2 роки тому +1

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

  • @iamnoob7593
    @iamnoob7593 3 місяці тому

    Man what a problem, Thank striver

  • @lakshya3324
    @lakshya3324 Рік тому +1

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

    • @coder_boy
      @coder_boy 6 місяців тому +1

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

  • @vamsikrishnagannamaneni912
    @vamsikrishnagannamaneni912 2 місяці тому

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

  • @amanasrani6405
    @amanasrani6405 6 місяців тому

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

  • @Tiyasa-d8f
    @Tiyasa-d8f 3 місяці тому

    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.

  • @paragroy5359
    @paragroy5359 10 місяців тому

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

  • @banothutharun2743
    @banothutharun2743 5 місяців тому +1

    understood brother 🤩

  • @unofficialshubham9026
    @unofficialshubham9026 Рік тому

    Thanks . Learnt a lot from you.

  • @djpsn7094
    @djpsn7094 Рік тому +1

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

  • @muditkhanna8164
    @muditkhanna8164 Рік тому +1

    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 ?

  • @BruceWayne-mf6ps
    @BruceWayne-mf6ps 9 місяців тому

    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.

  • @UECAshutoshKumar
    @UECAshutoshKumar Рік тому +1

    Thank you sir 😊

  • @kaichang8186
    @kaichang8186 3 місяці тому

    understood, thanks for the great video

  • @niteshverma8281
    @niteshverma8281 2 роки тому

    you know you are genius @striver

  • @rishabhagarwal8049
    @rishabhagarwal8049 2 роки тому

    Understood Sir, Thank you very much

  • @raghavmanish24
    @raghavmanish24 7 місяців тому +1

    thanku striver , it's crystall clear

  • @adebisisheriff159
    @adebisisheriff159 11 місяців тому

    Thanks Striver!!!

  • @yaswanthtogarapu8458
    @yaswanthtogarapu8458 Рік тому +1

    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
      @mrlord8519 9 місяців тому +1

      Same doubt bro....any lead now

    • @tasneemayham974
      @tasneemayham974 7 місяців тому +1

      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
      @Prateek_Mantry 5 місяців тому +1

      @@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
      @tasneemayham974 5 місяців тому

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

  • @abhishek__anand__
    @abhishek__anand__ Рік тому

    Great Explanation

  • @meetverma4812
    @meetverma4812 3 місяці тому +1

    can't we do this with simple BFS?

  • @NavyasriThalluri
    @NavyasriThalluri 3 місяці тому +1

    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
      @chandanc7545 14 днів тому

      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

  • @shivamgupta3520
    @shivamgupta3520 2 роки тому +2

    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
      @rishabhgupta9846 2 роки тому

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

    • @amansinghal4663
      @amansinghal4663 Рік тому +1

      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
      @shivamgupta3520 Рік тому

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

  • @komalkrishna7836
    @komalkrishna7836 2 роки тому

    Understood! Great explanation..

  • @amansingh.h716
    @amansingh.h716 3 місяці тому

    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

  • @amitp277
    @amitp277 Рік тому

    great explanation👏

  • @Prateek_Mantry
    @Prateek_Mantry 5 місяців тому +2

    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
      @FooBar-lb5wf 4 місяці тому

      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)

  • @manohar0742
    @manohar0742 Рік тому

    Happy teacher's day sir

  • @puspendrayadav8931
    @puspendrayadav8931 Рік тому +1

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

  • @mriduljain6809
    @mriduljain6809 Рік тому

    Understood Bhaiya

  • @adityasaxena6971
    @adityasaxena6971 Рік тому

    Understood✨✨

  • @tanujaSangwan
    @tanujaSangwan 3 місяці тому +1

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

  • @shaddyrogue9430
    @shaddyrogue9430 2 роки тому +7

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

  • @anubhavpabby6856
    @anubhavpabby6856 2 роки тому +10

    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
      @anubhavpabby6856 2 роки тому +1

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

    • @takeUforward
      @takeUforward  2 роки тому +9

      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
      @SatyamEdits 2 роки тому +11

      @@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
      @krishanpratap3286 2 роки тому +1

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

    • @b28venkatasivakalyankaliki81
      @b28venkatasivakalyankaliki81 Рік тому

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

  • @ayushranjan1265
    @ayushranjan1265 7 місяців тому

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

  • @-VLaharika
    @-VLaharika Рік тому

    Understood 👍

  • @ithcaironsthlotron5546
    @ithcaironsthlotron5546 2 роки тому +1

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

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

  • @Learnprogramming-q7f
    @Learnprogramming-q7f 7 місяців тому

    Thank you bhaiya

  • @subhashpatel5861
    @subhashpatel5861 Рік тому +3

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

  • @nehatanganiya5491
    @nehatanganiya5491 Рік тому +2

    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

  • @ankitanand1046
    @ankitanand1046 Рік тому

    Thank you

  • @The_Shubham_Soni
    @The_Shubham_Soni Рік тому

    UNDERSTOOD.

  • @udaykumarpg3874
    @udaykumarpg3874 2 роки тому +5

    Why can't we solve this problem using DP?

    • @somsk56
      @somsk56 3 місяці тому

      cause u r gay

  • @parshchoradia9909
    @parshchoradia9909 Рік тому

    understood SIr!

  • @priyanshvatsal9791
    @priyanshvatsal9791 Рік тому

    Understood 😇

  • @abhishekranjan8741
    @abhishekranjan8741 2 роки тому +1

    dp on trees striver plz

  • @ankitranjan88
    @ankitranjan88 Рік тому

  • @TarunKumar-cn6in
    @TarunKumar-cn6in 2 роки тому

    Understood 😀

  • @SHOURYASINGHAI-h8v
    @SHOURYASINGHAI-h8v 4 місяці тому

    understood !

  • @jayantgahlot2653
    @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]

  • @p38_amankuldeep75
    @p38_amankuldeep75 2 роки тому

    understood🧡❤🧡

  • @dank7044
    @dank7044 6 місяців тому

    did this on my own

  • @yahoo-kids
    @yahoo-kids Рік тому

    this video is good..

  • @mmbmmbmmb
    @mmbmmbmmb Рік тому +1

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

    • @tasneemayham974
      @tasneemayham974 7 місяців тому +1

      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?

  • @manasranjanmahapatra3729
    @manasranjanmahapatra3729 2 роки тому

    Understood!

  • @development5298
    @development5298 3 місяці тому

    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 ?

  • @aniketlal1657
    @aniketlal1657 Рік тому

    Could this be solved with DP?

  • @vakhariyajay2224
    @vakhariyajay2224 Рік тому +1

    Thank you very much. You are a genius.

  • @Sakuna172
    @Sakuna172 Рік тому

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

  • @suhaanbhandary4009
    @suhaanbhandary4009 Рік тому

    understood!!

  • @rushidesai2836
    @rushidesai2836 7 місяців тому +1

    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.

  • @SureshKumar-l2b7u
    @SureshKumar-l2b7u 6 місяців тому

    Understand

  • @subee128
    @subee128 Рік тому

    Thanks

  • @AyushSharma-ux4fk
    @AyushSharma-ux4fk Рік тому

    should we not use dp in this problem?

  • @girikgarg8
    @girikgarg8 Рік тому

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

  • @aryanbarnwal5645
    @aryanbarnwal5645 11 місяців тому

    why is dfs giving tle?

  • @keshavvyas2885
    @keshavvyas2885 2 роки тому

    Understood!!!

  • @siddharthmishra8233
    @siddharthmishra8233 Рік тому

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

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

  • @amansingh.h716
    @amansingh.h716 3 місяці тому

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

  • @lucy2003-d8p
    @lucy2003-d8p 5 місяців тому

    nice brother

  • @krisify
    @krisify 5 місяців тому

    Can this be solved using bs?

  • @akshatgosain3831
    @akshatgosain3831 Рік тому

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

  • @justanuhere
    @justanuhere 7 місяців тому

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

    • @tasneemayham974
      @tasneemayham974 7 місяців тому +3

      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
      @nownow1025 3 дні тому

      @@tasneemayham974 thanks

  • @abhijeetbasfore6816
    @abhijeetbasfore6816 2 роки тому

    Understood