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;
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.
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...❤❤
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.
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.
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
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 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
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
Try my Graph Concepts Playlist. I am sure you will love Graph after that ❤️🙏 ua-cam.com/play/PLpIkg8OmuX-LZB9jYzbbZchk277H5CbdY.html&si=0vH62FqyFSXJOjxd
class Solution { public: // int dijkstra(int n,int src,int dst,int k,vector&graph){ // } int findCheapestPrice(int n, vector& flights, int src, int dst, int k) { vectorgraph(n); for (auto it:flights){ graph[it[0]].push_back({it[1],it[2]});//node ,price } //return dijkstra(n,src,dst,k,graph); int mini=1e9; vectordistance(n,1e9); priority_queuepq; distance[src]=0; pq.push({{0,src},0}); while(!pq.empty()){ int node=pq.top().first.second; int dist=pq.top().first.first; int step=pq.top().second; pq.pop(); if(node==dst){ if(step
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)){
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!
One of the best solution out there for this question..
The explanation made things easy 🔥🔥🔥
Top Notch Content 🚀
Means a lot ❤️😇🙏
kaash mera college bhi aise padhata btw you are awsm
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
people are right. indeed you are the king of graphs
Legend on the way 👨💻 YOU ARE AMAZING
Means a lot 😇🙏❤️
You are a best master of dsa
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 😇🙏
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!
@@kareni7572 i dont understand why pq is not used? we are almost doing Djikstra here
Bohot bdhiya explanation sir❤
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.
Great Explanation bhai 🔥🔥❤❤❤❤
nice explanation bhaiya..
Best explanation for this question.
Thank you so much for watching 🙏😇
Just Awsm Explaination, Thank You🌟
amazing explanation 👌👌
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
He is like iron man in marvel 🔥
thank you sir
Simply understood
Great explanation, MIK. One thing is, I don't understand why pq is not used. We are almost doing Djikstra here?
Thanks a lot bhaiya ❤❤
Congrats for 19k subs 🎉🥳
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
You just invented Dijkstra's algorithm
Let's go😎😎
suggestion: please variable naming ko clear rkho,ese confusion create kr rhi h..
Sure thing.
Suggestion taken. Thank you ❤️🙏
Intution is very simple but when we go for code it becomes tough specially in java right?
great
❤️❤️❤️
Hi, can we solve this using Dijikstra algorithm?Why or why not?Seems like a similar problem to Network delay time
Just write Simple dijkstra code but with normal queue.
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
bhaiya please explain the time and space complexity separately
Masterpiece
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
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
Wasn't it just Dijkstra with Normal Queue???
This is modified BFS with Dijkstra Algorithm.
Ey sharma verma dharma. Aj ki daaru mery pay!
❤❤❤
❤❤
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.
Need to learn graph, I was ignoring graph
Try my Graph Concepts Playlist.
I am sure you will love Graph after that ❤️🙏
ua-cam.com/play/PLpIkg8OmuX-LZB9jYzbbZchk277H5CbdY.html&si=0vH62FqyFSXJOjxd
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
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
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.
class Solution {
public:
// int dijkstra(int n,int src,int dst,int k,vector&graph){
// }
int findCheapestPrice(int n, vector& flights, int src, int dst, int k) {
vectorgraph(n);
for (auto it:flights){
graph[it[0]].push_back({it[1],it[2]});//node ,price
}
//return dijkstra(n,src,dst,k,graph);
int mini=1e9;
vectordistance(n,1e9);
priority_queuepq;
distance[src]=0;
pq.push({{0,src},0});
while(!pq.empty()){
int node=pq.top().first.second;
int dist=pq.top().first.first;
int step=pq.top().second;
pq.pop();
if(node==dst){
if(step
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)){