I started seeing this channel when it was having 100 subscribers now it's nearly above 10k all bcoz of clearly explaining the concept with same belief I expect you to start contest solutions
INTUITION - As in the question least number was given src,target was given hence thought of bfs /* Think of question as a Metro use case , here you have to start your journey from your nearest metro station that is in this case is the source Once you have seated in the metro , you can go to n metro station and if in this n station one is your destination(target) station then well and good you reached your target, but if target is not on this route then you have to switch metro , so from a particular station check which metro is available and sit on that metro which you have not taken before and repeat the same process */ int numBusesToDestination(vector& routes, int source, int target) {
//No need to take metro if(source==target){ return 0; } int n=routes.size(); //to store from each metro station which metro trains are available unordered_map adj; for(int metro=0;metro
i assumed the bus routes as metro lines and the question got way easier, all they are asking the minimum metro lines to switch to reach the destination, the intuition also works with the examples you can relate to. i was confused thinking its asking the shortest path.
Firtst tried to BFS through the adjacent bus stops but got MLE in case 43. Then tried BFS for bus routes keeping track of the bus stops in the bus routes using map and vector. It got accepted. Now watching your video for most optimal solution. ❤
@@darkstudio3170 actually I kept the bus count in a map for each of the bus stations. Take an example like below routes = [[1,2,7],[3,6,7]], source = 1, target = 6 1 has two adjacents 2 & 7 2 has two adjacents 1 & 7 3 has two adjacents 6 & 7 6 has two adjacents 3 & 7 7 has four adjacents 1, 2, 3 & 6 (cause you can visit all these nodes from 7 directly) when I visit '1' (source) for the first time, I set all its adjacent bus route count value to '1' in the map. that means map[1] = 0; map[2] = 1; map[7] = 1; then for '2': all its adjacent are already visited. for '7': 1 & 2 are already visited, but 3 and 6 was not visited before. therefore, map[3] = map[7] + 1 = 1 + 1 = 2; map[6] = map[7] + 1 = 1 + 1 = 2; when I found the target then returned the value stored in the map. like return map[6]; if(map.find(6) == map.end()) return -1; let me know if its still not clear.
sir I think the Time complexity will (m*k*m) instead of (m*k^2) as in the worst case in the queue we would be visiting each bus and for each bus we would be exploring the stop the bus will be visiting and for that stop we will be exploring the buses which will that visit that stop. Please correct me sir if I am wrong .
That source can be present in multiple routes (indices). We must be able to know from which possible routes(bus) we can start. Hence we must store the indices in which source is present
For this approach, I was getting TLE. 43/49 were passing. public int numBusesToDestinationv1(int[][] routes, int source, int target) { Map adj = new HashMap(); for (int[] route : routes) { for (int i = 0; i < route.length; i++) { for (int j = i + 1; j < route.length; j++) { adj.computeIfAbsent(route[i], k -> new ArrayList()).add(route[j]); adj.computeIfAbsent(route[j], k -> new ArrayList()).add(route[i]); } } } for (Map.Entry entry : adj.entrySet()) { System.out.println(entry.getKey() + " : " + entry.getValue()); } Queue queue = new ArrayDeque(); queue.add(new Pair(source, 0)); Set visited = new HashSet(); visited.add(source); while (!queue.isEmpty()) { Pair node = queue.poll(); int u = node.getKey(); int bus = node.getValue(); if (u == target) return bus; if (adj.containsKey(u)) { for (int v : adj.get(u)) { if (!visited.contains(v)) { visited.add(v); queue.add(new Pair(v, bus + 1)); } } } } return -1; }
Because we want to traverse level by level in BFS. Always remember that when we want to find a target in shortest distance, always prefer writing this way of doing BFS. It traverses level by level. sz = number of nodes in current level
@@codestorywithMIK Ok will do this way. But just I am curious why in any article/video i referred so far, i haven't found this way, is it like they preassume that there is only one source they are starting with? Thanks
Sir your content is amazing but the presentation of thumbnails are not upto the mark which restricts the viewership... If you want to improve let's connect...as a thumbnail designer may be i can help you with that
Hi there, Thank you so much for this feedback ❤️ Actually i have received this couple of times. I am curious now and want to know what are the things missing in the thumbnail. Can you please jot down some points ? Let me then think through it.
@@codestorywithMIKsure sir Look due to the high supply of videos on UA-cam there are lot of options for viewers and your teaching method is super easy but thumbnails make it seems difficult at the first place... Second visually appealing thumbnails boost the ctr for the channel and eventually UA-cam promote it as more viewer's show interest in the video but in your case they are not appealing so viewers who know you watch your videos coz they are aware of your content but for new viewers you need to make them click or create curiosity there are more technicals things on which you can work and genuinely if you see UA-cam as a serious game i would love to have a meeting with you and we can discuss further.
Happy Diwali to everyone of you.
My love and blessings to everyone ❤❤❤❤🪔🪔🪔
happy diwali mik bhaia💫💫💫💫
Happy diwali bhai
happy diwali bhai
Happy Diwali🪔
I started seeing this channel when it was having 100 subscribers now it's nearly above 10k all bcoz of clearly explaining the concept with same belief I expect you to start contest solutions
💯
No channel can beat your way of explanation. It's different and unique.
I see many solution but your solution is very very nice thanks a lot !!
(This question asked in Phonepe Interview 2023-sept.)
You are most welcome
Thank you so much for sharing company tag ❤️🙏
INTUITION -
As in the question least number was given src,target was given hence thought of bfs
/*
Think of question as a Metro use case , here you have to start your journey from your nearest metro station that is in this case is the source Once you have seated in the metro , you can go to n metro station and if in this n station one is your destination(target) station then well and good you reached your target, but if target is not on this route then you have to switch metro , so from a particular station check which metro is available and sit on that metro which you have not taken before and repeat the same process
*/
int numBusesToDestination(vector& routes, int source, int target) {
//No need to take metro
if(source==target){
return 0;
}
int n=routes.size();
//to store from each metro station which metro trains are available
unordered_map adj;
for(int metro=0;metro
i assumed the bus routes as metro lines and the question got way easier, all they are asking the minimum metro lines to switch to reach the destination, the intuition also works with the examples you can relate to. i was confused thinking its asking the shortest path.
Firtst tried to BFS through the adjacent bus stops but got MLE in case 43. Then tried BFS for bus routes keeping track of the bus stops in the bus routes using map and vector. It got accepted.
Now watching your video for most optimal solution. ❤
I am glad you tried BFS through adjacent bus as well. Although it gives MLE but it teaches us many things. Different approaches often teach us a lot.
When you are doing BFS through adjacent bus , how did you maintain the number of bus counts, did you tried each path and calculate min bus count ?
@@darkstudio3170 actually I kept the bus count in a map for each of the bus stations.
Take an example like below
routes = [[1,2,7],[3,6,7]], source = 1, target = 6
1 has two adjacents 2 & 7
2 has two adjacents 1 & 7
3 has two adjacents 6 & 7
6 has two adjacents 3 & 7
7 has four adjacents 1, 2, 3 & 6 (cause you can visit all these nodes from 7 directly)
when I visit '1' (source) for the first time, I set all its adjacent bus route count value to '1' in the map.
that means
map[1] = 0;
map[2] = 1;
map[7] = 1;
then for '2': all its adjacent are already visited.
for '7': 1 & 2 are already visited, but 3 and 6 was not visited before.
therefore,
map[3] = map[7] + 1 = 1 + 1 = 2;
map[6] = map[7] + 1 = 1 + 1 = 2;
when I found the target then returned the value stored in the map. like
return map[6];
if(map.find(6) == map.end()) return -1;
let me know if its still not clear.
Wow this was a tough BFS question. Thanks again for brilliant explanation.
super duper clean. I almost solved it on my own, just got MLE . Using index in map was really smart.
Very nice explanation sir, Thank you!
happy diwali bhaiaya .... aaj aapki story sunke problem sol karneka try kiya aur ho gaya hehehehheehhe :) :) :) :) ....... love u bhaiaya 😘😘😘😘😘
Happy Diwali Bhaiya .. Day 49 completed .. Thank You 🙏🙏🙏🙏..
Will be waiting eagerly and I will make sure I will remember you for every contest and I hope u start it as soon
bhahiya leetcode k contests k bhi solutions post kiya kro please and please post 1 video of begginer dp playlist daily
Happy Diwali Bhaiya 🎆🎆🎆🎆.
Happy Diwali Sir :)
Happy diwali bhaiya!
The best explanation 😊 ,also Happy Diwali 🪔
Awesome explanation bro.
Best ❤
Thanku bhaiya ❤
beautiful! ❤
happy diwali 🪔
sir please contest ke solutions bhi upload kiya karo
Too good
Happy diwali sir
sir I think the Time complexity will (m*k*m) instead of (m*k^2) as in the worst case in the queue we would be visiting each bus and for each bus we would be exploring the stop the bus will be visiting and for that stop we will be exploring the buses which will that visit that stop.
Please correct me sir if I am wrong .
A humble request , if you could post leetcode contest 3rd and 4th question.
❤❤❤❤❤❤❤
since we want to store the source int the queue , why we are not directly doing this q.push(source) as the source is already given ??
That source can be present in multiple routes (indices). We must be able to know from which possible routes(bus) we can start. Hence we must store the indices in which source is present
@@codestorywithMIK thnx , understood
You missed the edge case where source is not present in any of the routes I guess..
This diwali I expect @codestorywithmik to start discussing leetcode contest qns for better improvement of student coding knowledge
Will definitely start this on a regular basis. 🙏🙏😇😇❤️❤️
And wish you a very happy and prosperous diwali ❤️❤️
happy Diwali bhaiya, idk plz aap time nikal kr contest ka solution video bnao na plzzzz 😢
Coding Mohan ko follow Kiya kro. Uska seg tree playlist acha h.
For this approach, I was getting TLE. 43/49 were passing.
public int numBusesToDestinationv1(int[][] routes, int source, int target) {
Map adj = new HashMap();
for (int[] route : routes) {
for (int i = 0; i < route.length; i++) {
for (int j = i + 1; j < route.length; j++) {
adj.computeIfAbsent(route[i], k -> new ArrayList()).add(route[j]);
adj.computeIfAbsent(route[j], k -> new ArrayList()).add(route[i]);
}
}
}
for (Map.Entry entry : adj.entrySet()) {
System.out.println(entry.getKey() + " : " + entry.getValue());
}
Queue queue = new ArrayDeque();
queue.add(new Pair(source, 0));
Set visited = new HashSet();
visited.add(source);
while (!queue.isEmpty()) {
Pair node = queue.poll();
int u = node.getKey();
int bus = node.getValue();
if (u == target) return bus;
if (adj.containsKey(u)) {
for (int v : adj.get(u)) {
if (!visited.contains(v)) {
visited.add(v);
queue.add(new Pair(v, bus + 1));
}
}
}
}
return -1;
}
since source and target is given cant we do it using dijkstra or any of the algorithms
Abe minimum cost nhi minimum buses btani h 😂. Mtlb minimum nodes traversed.
why you included while(sz--){...code...} inside while(!que.empty()){...code...}?
Because we want to traverse level by level in BFS.
Always remember that when we want to find a target in shortest distance, always prefer writing this way of doing BFS. It traverses level by level.
sz = number of nodes in current level
@@codestorywithMIK Ok will do this way. But just I am curious why in any article/video i referred so far, i haven't found this way, is it like they preassume that there is only one source they are starting with? Thanks
we also use dp sometimes than how to identify whether we have to use dp or graph? any trick mik bhaiya?@@codestorywithMIK
I tried to apply dijkstra but it failed
Fail hi hoga cuz tujhe minimum buses btani h, cost nhi. Moreover source node multiple routes mein available h.
❤❤❤
Sir your content is amazing but the presentation of thumbnails are not upto the mark which restricts the viewership... If you want to improve let's connect...as a thumbnail designer may be i can help you with that
Hi there,
Thank you so much for this feedback ❤️
Actually i have received this couple of times. I am curious now and want to know what are the things missing in the thumbnail. Can you please jot down some points ?
Let me then think through it.
@@codestorywithMIKsure sir
Look due to the high supply of videos on UA-cam there are lot of options for viewers and your teaching method is super easy but thumbnails make it seems difficult at the first place... Second visually appealing thumbnails boost the ctr for the channel and eventually UA-cam promote it as more viewer's show interest in the video but in your case they are not appealing so viewers who know you watch your videos coz they are aware of your content but for new viewers you need to make them click or create curiosity there are more technicals things on which you can work and genuinely if you see UA-cam as a serious game i would love to have a meeting with you and we can discuss further.
Man this sucks, couldn't solve this easy problem 😢😢😢😢
please sir
Happy diwali Bro! Making life easy for eveyone!🪔🪔❤
please sir
please sir