Cheapest Flights Within K Stops | Graph | [CODE + Explaination] | Amazon | GFG 🔥

#graph #competitiveprogramming #coding #dsa
Hey Guys in this video I have explained with code how we can solve the problem 'Cheapest Flights Within K Stops'.
Join our Telegram Channel for more Information
🔰 Telegram Channel Link = t.me/CodeLibrary1
🔰 Array question Playlist = • Love Babbar DSA 450 Qu...
🔰 String question Playlist = • Love Babbar DSA 450 Qu...
🔰 Searching and Sorting question Playlist = • Love Babbar DSA 450 Qu...
🔰 Binary Tree question Playlist = • Love Babbar DSA 450 Qu...
🔰 Dynamic Programming question Playlist = • Love Babbar DSA 450 Qu...
🔰 RoadMap of Web Development = • 🔴 Web Development Road...
🔰 Roadmap for Dynamic Programming = • Complete Roadmap for D...
🔰 Great Strategy to solve DSA = • Great Strategy to solv...
🔰 My Journey to 5 star at codechef = • My Journey to 5 Star a...
🔰 Love Babbar DSA Sheet : drive.google.com/file/d/1FMdN...
Follow us on Instagram:
🔰 Shailesh Yogendra : / shaileshyogendra
🔰 Yogesh Yogendra : / i_am_yogesh_here
Follow us on LinkedIn:
🔰 Yogesh Yogendra : / yogesh-yogendra-26bbb518a
🔰 Shailesh Yogendra : / shailesh-yogendra-8b13...
Hope you like it. Comment if you have any doubt
LIKE | SHARE | SUBSCRIBE

[@CodeLibrary]

Update
Recently Leetcode has updated its test cases so the Priority queue solution is not getting Accepted it's giving TLE. So I have to do this question by some different approach.
I will update the solution in the next video.

[@Prodcater]

bana do bhaiya naya vide ispe plz

[@AbhishekKumar-be7tx]

To tackle TLE just use a map saying seen_stop, idea is whenever we see some already visited node we check whether st that time the curr stops was lesser or not - if less then set that stops to that node at seen_stop else don't add it into pq again.

[@akshatgupta2607]

@@AbhishekKumar-be7tx thanks mate :)

[@RajeevKumar-fb3in]

Abe TLE de rha hai

[@aniketbhore4002]

bro i think hindi + english combination is good...just like the previous videos.

[@CodeLibrary]

okay

[@Nitin-wy8wh]

thanks buddy, you have saved my entire night.

[@harshalgarg1149]

Thanks bro

[@kartikaymahajan9591]

giving tle

[@kumarakash5219]

Wether we can use bellman for algorithm?

[@MANOJSINGH-iz7lv]

simple use Bellman-Ford algo.
and compare previous cost vector
# define MAX 1e9
class Solution {
public:
int findCheapestPrice(int n, vector& flights, int src, int dst, int k) {
vector cost(n,MAX);
vector pre_cost;
cost[src]=0;
k++;
while(k--){
pre_cost.assign(cost.begin(),cost.end());
for(auto i:flights){
int a=i[0];
int b=i[1];
int w=i[2];
cost[b]=min(cost[b],pre_cost[a]+w);
}
}
if(cost[dst]==MAX) return -1;
return cost[dst];
}
};

[@Impromptu21]

U r using dijkstras algo which will not work here bcoz lets say we have connections 0-->1 cost 100, 0-->2 cost 400, 1--->2 cost 100, 2-->3 cost 100 and we want to go from 0 to 3 with 1 stops here dijkstras will go from 0-->1 and then 1-->2 and then it will realize that now stops are not available as we have taken max 1 stops until now but as we have now updated the distance with 200 at node 2 we will not be able to get correct ans.As correct ans is 0-->2 and then 2-->3 with cost 400+ 100.

[@justarandomguy6106]

I think that this testcase will work because it will return at A because steps are greater than given and we didn't find the value

[@ujjwalmittal3785]

Tell me one thing anyone plz . Though this approach is giving tle now , but why in this solution we have not used distance vector as we usually do in djikstra algo

[@nikhilkamboj4376]

Hello Brother
One optimize tip : All node which we pop out from queue (Node which are relaxed ) should' we mark processed using array .
Since processed node finish there job there is no point to put them again in queue.
But with one condition node which not able to process properly because of exceed boundary condition should not be mark processed.
If we think of it like Dijkstra with min heap

[@CodeLibrary]

yaa like this we can improve little bit.........let me go through once

[@viratkohli-jr6md]

is the algo used is some sort of dijkshtra?

[@anuragsingh-gj4vn]

bro please create a video on the updated solution to this problem

[@himanshunegi5228]

if there is cycle in graph them????????

[@ayushagrawal9031]

Bhai yeh same code tle de raha hai 😐

[@ece116pranaykumar4]

tle aa rha

[@sohammehta8815]

This approach gives TLE!!

[@tekbssync5727]

yess, then what to do ?

[@CodeLibrary]

Ya recently leetcode has updated the testcases

[@akashjaiswal6478]

@@CodeLibrary bro please make a video on new solution, don't know how to solve this tle;

[@mridulgupta9841]

which softwar and device do you use to write

[@namanftw8641]

HINDI MAI HI KARUUUUUUUUUUUU

[@ratneshpndy7186]

Bhai coding woding to sab theek hai
Par ek baar shailesh ka ek beatboxing ka video v daal yaahan 😜😜
Abey hmko pehchante to ho na be k bhul gye😜

[@CodeLibrary]

Haa yaar...... Shailesh wale channel me upload karte hai beatboxing wala😀

[@ratneshpndy7186]

@@CodeLibrary oohh acha acha channel ka name kya hai??

[@CodeLibrary]

Shailesh Yogendra

[@shubhampokhriyal8491]

Which slide is this ques slide..?? Can you send it

[@tusharshaily]

Love Babar 450

[@shubhampokhriyal8491]

@@tusharshaily can you send link

[@sanskarjain2730]

@@shubhampokhriyal8491 drive.google.com/file/d/1FMdN_OCfOI0iAeDlqswCiC2DZzD4nPsb/view

[@rahulbhati3079]

it is giving tle

[@snehabaser3155]

Yes

[@ankitparashar8730]

@@snehabaser3155 yes

[@devilronak7262]

can plz anyone tell , how to fix this TLE

[@rahulbhati3079]

HINDI IS BEST BRO

[@inderjeetchaudhary6815]

ye sb baad m btate hn explore krke.......let explore it's very funy😂 bhai

[@PatelFromPatna]

why have we not used visited array..like for eg what if the node 2 was connected to node 0 and node 5 simultaneousy. Plz answer!!

[@LegitGamer2345]

you should use boolean array , but in this case even if we dont use boolean array it will work because youll be terminating when stops>k

[@LegitGamer2345]

my previous reply is not correct , i tried submitting it using visited array and it failed , then i tried submitting it without using visited array it passed all testcases , the reason why we are not using visited array is because if u do use visited array , you will not be able to visit the already visited node , and you may want to visit already visited node in this question because there might still exist a possible path having shorter length

[@tusharshaily]

we want multiple occurrences of node and then filter out using the stops

[@LegitGamer2345]

@@tusharshaily use visited array and try submitting on leetcode and you will find a counter example

[@SatyamKumar-ts2jh]

@@LegitGamer2345 If you want to use visited array, you can use a 2d array, with vertex and the number of stops left as coordinates of the 2d matrix. But that wont be of much benefit, and will use up a lot of space as well, hence its not of much use

[@devilronak7262]

Bro this is giving TLE

[@snehabaser3155]

This gives tle

[@CodeLibrary]

Ya recently leetcode has updated the testcases

[@harshagarwal9057]

Absolutely wrong solution, Will get into infinite loop in case of directed cycle. What a waste of time..!

[@tekbssync5727]

bellman wala batao bhai , ye TLE de rha hai, comment wagera nhi padhte ho kya ab tum log.
Accha mai bhul gya tha , bada channel ho gya hai !!! 😅

[@CodeLibrary]

are comments read karta hu bro.......dusra approach soch ke banata hu naya video

[@satveeryadav2188]

giving tle