Cheapest Flights Within K Stops | GOOGLE | BFS | Explanation ➕ Live Coding
Vložit
- čas přidán 25. 01. 2023
- WhatsApp Community Link - whatsapp.com/channel/0029Va6k...
This is the 15th Video on our Graph Playlist.
In this video we will try to solve a good and classic Graph problem "Cheapest Flights Within K Stops" (Leetcode-787).
If you have been following my "Graph Concepts & Qns" playlist , then these Qns will become very easy.
Problem Name : Cheapest Flights Within K Stops
Company Tags : GOOGLE
My solutions on Github : github.com/MAZHARMIK/Intervie...
Leetcode Link : leetcode.com/problems/cheapes...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My GitHub Repo for interview preparation : github.com/MAZHARMIK/Intervie...
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview #interviewtips
#interviewpreparation #interview_ds_algo #hinglish
You are king of graph
Sir please java code bhi add karna c++ nhi aati sabko like striver
Added Java in the comment by JJ
Hope that will help 😊
Nice please do it for all future videos
No one can teach graph so gracefully like you do. You are different
People will soon know about you
Happy Republic Day bhai. Thanks, below is the Java implementation:
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
int[] distance = new int[n];
Arrays.fill(distance, Integer.MAX_VALUE);
Map adj = new HashMap();
for(int [] flight : flights){
adj.computeIfAbsent(flight[0], value -> new ArrayList()).add(new Pair(flight[1], flight[2]));
}
// bfs
Queue q = new ArrayDeque();
q.add(new Pair(src, 0));
distance[src] = 0;
int steps = 0;
while(!q.isEmpty() && steps 0){
int u = q.peek().node;
int price = q.peek().price;
q.poll();
if (!adj.containsKey(u))
continue;
for(Pair p : adj.get(u)){
int v = p.node;
int cost = p.price;
if(distance[v] > price + cost){
distance[v] = price + cost;
q.add(new Pair(v, price+cost));
}
}
}
steps++;
}
return distance[dst] == Integer.MAX_VALUE ? -1 : distance[dst];
}
}
class Pair {
int node;
int price;
Pair(int _node, int _price){
this.node = _node;
this.price = _price;
}
}
Your voice is very friendly, keep up the good work
Glad to finally understand it cleanly! Much Appreciated!
The explanation made things easy 🔥🔥🔥
One of the best solution out there for this question..
people are right. indeed you are the king of graphs
You are a best master of dsa
kaash mera college bhi aise padhata btw you are awsm
Bohot bdhiya explanation sir❤
Just Awsm Explaination, Thank You🌟
amazing explanation 👌👌
nice explanation bhaiya..
Nice that I found your channel , Please never stop to make videos , Eventually you will be famous for sure.
bro i done all concept of still not able to solve question but way of your teaching i am sure one day i will be master in DSA.thanks alot for this type of content.
Thanks Sachin ❤️
Welcome to my channel 😊
@@codestorywithMIK waiting many more dsa concepts video specially on recursion that make too fear of cp
Legend on the way 👨💻 YOU ARE AMAZING
Means a lot 😇🙏❤️
Great Explanation bhai 🔥🔥❤❤❤❤
bhaiya why cant we do this using Dijkstras because in your Graph concept and questions playlist you mentioned in questions where "source" and "destination" is mentioned we usually use Dijkstras. Moreover don't we use BFS in shortest path questions when graph is unweighted or is there no as such restriction. One last request can you please clarify when to use dijkstras and when to use BFS in such questions.
last me bhaiya thank you so much for your efforts your teaching style is really unique.
This video is using modified Dijkstra algorithm but using queue. if we use priority queue then we will only process min prices nodes and can miss nodes going to correct answer, so eliminate this scenario dijkstra is implemented using queue.
@@nirmalgurjar8181 bcuz here stops are more prioritizing than distance, Dijkstra will surely find shortest path but it may use more stops than required
@@ayaanrashid960 not just stop, its stop + cheapest. queue will take care of stop and diksktra will take care of cheapest price. That's why its modified Dikstra algorithm.
Simply understood
Waiting for the next concept video, This is great video 😁
Yep soon.
I hope we all are now able to solve Graph Qns.
Hope we all grow more
Thanks a lot bhaiya ❤❤
thank you sir
Top Notch Content 🚀
Means a lot ❤️😇🙏
Best explanation for this question.
Thank you so much for watching 🙏😇
A imp consderation , we can't use PriorityQueue here (my first instinct was to use pQ) , because it might happen that the shortest path to the des can have more number stops and it blokes the other larger path which have less number of stops.
Was looking for this comment!
Congrats for 19k subs 🎉🥳
Masterpiece
We can also omit the isempty check from the while loop as in constraints it is given that k is always less than n .....in simple word we are doing relaxation of nodes for k times and also thank you for providing such content your way of explaining concepts is really nice...❤❤
Thank you so much 😇🙏
He is like iron man in marvel 🔥
Let's go😎😎
Hi, can we solve this using Dijikstra algorithm?Why or why not?Seems like a similar problem to Network delay time
great
❤️❤️❤️
outstanding explanation man!!
but ye intuition building kaise achi hogi?
sometimes i just go on another track.
kuch jyada hi soch leta hu😅😅
Thanks Satyam.
Actually I have noticed , intuition generally comes from the most basic thing that we are aware of.
For example: Here in this Qn, I thought about the most basic thing we can think of about Graph that is the BFS.
And then i run around BFS until I figure out what are the cases required for solving a particular qn.
I would always suggest strengthening in the basic and obvious concepts which we tend to miss because of thinking too much.
I am pretty sure this will improve with time and with solving more and more Qns
@@codestorywithMIK Oh!! Definitely gonna use this tip now on. Thanks for clearing this👍
@@satyamjha37 helpful
everyone thinking of dijkstra and using priority queue
but i think hhere we are not using priority queue
because its not about the shortest or cheapest path but with cheapest and k stops
so if we use priority queue and condition of k stops then it may be possible we can not reach destination
again got stuck with this thought thank god i commented this thing on youtube
Intution is very simple but when we go for code it becomes tough specially in java right?
You just invented Dijkstra's algorithm
suggestion: please variable naming ko clear rkho,ese confusion create kr rhi h..
Sure thing.
Suggestion taken. Thank you ❤️🙏
❤❤
❤
❤❤❤
❤🔥
here we are not maintaining seen set to mark visited, what if there is cycle b/w node
will go for max k stops, so it wont end up in an infinite cycle
Ey sharma verma dharma. Aj ki daaru mery pay!
Bhaiya ye djikstras se bhi to kar sakte the na BFS ke badle?
Yes. And with many other approaches.
I will soon share other approaches too
@@codestorywithMIK brother i am currently in 2nd year
Currently i have one full year for coding
Bhai plss ek baari aap trees and graphs ka ek tagda playlist banado 😭😭 mere bhut help ho jaege
Sure Gurnoor,
Graphs Concept playlist is in progress (you can see it), i have explained there from scratch.
And i will create other playlists soon.
Currently travelling and will be on break for 3 weeks.
Will be back with more awesome contents
@@codestorywithMIK Yup and please compare their time complexities too
@@codestorywithMIK 😌😌 ok bhaiya aapka samjhane ka method bilkul hatke hai aap ache see trees graphs karado mera kaam bn jayega
This is modified BFS with Dijkstra Algorithm.
Need to learn graph, I was ignoring graph
Try my Graph Concepts Playlist.
I am sure you will love Graph after that ❤️🙏
czcams.com/play/PLpIkg8OmuX-LZB9jYzbbZchk277H5CbdY.html&si=0vH62FqyFSXJOjxd
if there is a cycle then how we gonna handle that ?
We are only adding to queue if distance is lesser. It can only happen finite number of times
Some extra test case added and this code is giving wrong answer
It seems to passing for me
Tried Submission today also - leetcode.com/submissions/detail/1183541862/
Can you kindly check again.
Video on bellman's approach?
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
for (int i = 0; i
Soon in my Graph Concepts playlist after i teach that topic 😊
It gives TLE
It seems to passing for me
Tried Submission today also - leetcode.com/submissions/detail/1183541862/
Can you kindly check again.
WHILE (N--) KARKE KYU BFS KIYA CAN U EXPLAIN
To cover all nodes in current level at once.
This is the way we do BFS whenever we want to process all nodes level by level
while(N--- )kyu kr rhe ,ek baar explain kr skte ho please...wo smjhe nhi
It can also be written as
while(N > 0) {
//do stuff
N- - ;
}
Both are same.
bhaya mera tle arra h
Can you share your code
most possible problem according to me is ........ shayad tumne q.pop() ; nahi kiya hoga please check
RECURSION + MEMO:::
class Solution {
int dp[102][102];
public:
int getCheapestPrice(int currentCity, int& destination, int remainingStops, vector& adjList) {
if (currentCity == destination) { //it will cost 0 to reach destination
return 0;
}
if (remainingStops < 0) {//invalid flight path
return INT_MAX;
}
if (dp[currentCity][remainingStops] != -1) {
return dp[currentCity][remainingStops];
}
int minPrice = INT_MAX;
//explore all neighbor city and return min price
for (auto& neighbor : adjList[currentCity]) {
int neighborCity = neighbor.first;
int price = neighbor.second;
int nextPrice = getCheapestPrice(neighborCity, destination, remainingStops - 1, adjList);
if (nextPrice == INT_MAX) { //if invalid path skip(can cause overflow)
continue;
}
minPrice = min(minPrice, price + nextPrice);
}
return dp[currentCity][remainingStops] = minPrice;
}
int findCheapestPrice(int numCities, vector& flights, int source, int destination, int maxStops) {
// source -> {destination, price},.....
vector adjacencyList(numCities);
for (auto& flight : flights) {
int source = flight[0];
int destination = flight[1];
int price = flight[2];
adjacencyList[source].push_back({destination, price});
}
memset(dp, -1, sizeof(dp));
int cheapestPrice = getCheapestPrice(source, destination, maxStops, adjacencyList);
return cheapestPrice == INT_MAX ? -1 : cheapestPrice;
}
};
your java code change this line Listneighbors=adj.getOrDefault(u,Collection.emptyList) change this.
if(!adj.containsKey(u)) continue;
for(int[]neighbor:adj.get(u)){