Shortest Path Visiting All Nodes | Clean | Simple | Intuitive | BFS | GOOGLE | Leetcode-847 |
Vložit
- čas přidán 16. 09. 2023
- iPad PDF Notes - github.com/MAZHARMIK/Intervie...
This is the 36th Video on our Graph Playlist.
In this video we will try to solve a very good Graph Problem "Shortest Path Visiting All Nodes" (Leetcode - 847)
Trust me, this will no longer be a Hard Problem. I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
If you have been following my "Graph Concepts & Qns" playlist , then these Qns will become very easy. Find the Link for that below.
We will do live coding after explanation and see if we are able to pass all the test cases.
Problem Name : Shortest Path Visiting All Nodes
Company Tags : GOOGLE
My solutions on Github (C++ & JAVA) : github.com/MAZHARMIK/Intervie...
Leetcode Link : leetcode.com/problems/shortes...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My GitHub Repo for interview preparation : github.com/MAZHARMIK/Intervie...
Subscribe to my channel : / @codestorywithmik
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips
#interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook
OMG! Never seen such fine explainations on all of youtube. It's really important to know and understand the thinking process for a question, if not more important than the solution itself because it helps you to think in similar ways for similar questions. Thought process is really helpful in coding interviews.
Really good work. Keep it up, Sir!
Thank you so much Akash ❤️😇🙏
Your comment made my day ❤️❤️
💯
Totally agree
I can bet, no one can teach intuition building like you. Bring any famous youtuber, this guy stands alone 🔥🔥🔥
Thank you so much ❤
Hi Everyone,
If you want the Complete Dry Run of Entire Example , let me know, I will create another video for that ❤️❤️❤️
Thank you all
Yes
Bhai maine khud se dry run karliya. Thanks to you.
sir explain so well that we dont need explanation again
@showsshorts4696 😇❤️🙏
The intuition building was phenomenal 😲😲😲🔥🔥🔥
Time Complexity : 0(2^N * N^2).
Notice the while loop that performs the BFS traversal of the graph.
In the worst case, the while loop can run 2^N iterations, where N is the number of nodes in the graph. This is because the program explores all possible combinations of nodes using bit masking i.e. each bit can be either 0 or 1 (2 possibilities) --> 2^N
Within each iteration, there is a nested loop that iterates through the neighbors of the current node. In the worst case, this inner loop iterates N times for each node.
So, the overall time complexity is 0(2^N * N^2).
Thanks a lot
This man deserves so much more yyr. Never Ever seen someone with such a clean and elegant code, with dry run and complete intuition, ill do my best to make sure my friends start studying from you only from now on.
It means a lot to me. Thank you so much ❤️😇
indeed
next level teaching
Thank you so much 🙏😇❤️
One of the finest explanations. I did the dry run on my own. Loved the intuition building.
Thanks a lot
You are an inspiration bro ❤❤
Means a lot to me 🙏🙏❤️❤️
This is nothing but pure gold thank you so much!
Means a lot 😇❤️
Hi Mik,
I had another question I know you have iterated in the video but just for clarification I wanted to know for any problem in graphs if there is a shortest path if we use BFS from any index will it by default be the shortest path?
Regards,
Karthik Kaushik
You deserve millions of subscribers. Never seen dedication like this.
Hats off to your explanation! Your thought process and your strategy for building intuition are outstanding! I do have a small suggestion, though. It would be greatly helpful if you could include inline comments when writing functions in your Git repository. Thank you!
Feedback taken. Thank you so much for the suggestion. I will definitely include more comments in my code in github 😇🙏
Thank you.
You explain things very well
Amazing❤❤
Next Level Undertstanding🔥🔥🔥
Salute hai bhai aise unique teaching skill ko. No one clears intuition better than you.
Sir it wud be helpful if u make a question list video(leetcode )which covers all type of problems..and. after doing those problems we wud be in a position to tackle any other problems..pls sir
From past 2-3 weeks i am asking this
I think right now He only has C++ solutions. We should contribute to his repo in our respective programing language, so it's helpful for other people. He's usually realy busy. He travels a lot and on top of that he makes this amazing videos to explain stuff.
Hi Tejaswi,
Would you confirm, are you referring to a DSA sheet like ??
bhai please bana do ek sheet because bht questions h leetcode p or waha se selective or bht acche questions krna is very difficult, apki teaching style or knowledge bht achi h bhai@@codestorywithMIK
@@codestorywithMIK yes sir
@@codestorywithMIK congratulations for 9k subscribers
Wonderful explanation ! I remember struggling with this question sometime back, you made it so intuitive!
I am so glad the intuition was helpful 😇❤️🙏
just because of you meri leetcode consistency maintained hai. 50 days ho chuka hai max streak. thank you so much for your amazing content ❤🙌
50 days 🔥🔥👌👌👌
Keep it up
Thank you 😇❤️🙏
thanks for the superb explanation
Thank you so much 😇🙏
Seeing first time your video, awesom skill bro. Keep it up.
Thank you 😇🙏
Welcome to my small channel ♥️
Thanku Bhaiya ❤ and congratulations for 9k
Thank you so much for trusting my channel 🙏😇❤️
Great explanation!!
Thank you so much 😇🙏❤️
If you think I should create a separate video in which I should do a complete dry run for the video, then let me know, i will make one for sure ❤️❤️❤️
Subscribed for this solution, i was confused about implementation you cleared my doubt how using bfs will always give us shortest path if put all nodes into queue
Thank you so much ❤️🙏😇
Bhai yard... I'm Wordless... You are so underrated yaar... you deserve many more subs... Love you bhai 🥰🥰🥰..... And thank you so much yarn bhai.
Thank you so much. It means a lot to me ❤️🙏
At 28:10 , When you have popped (0,1), For node 0, you have only added the first neighbour of it. I think you have to add 2 and 3 as well. You directly went to next node.... I'm not pointing out, just asking, Correct me if I'm wrong
Yes yes, you are 100% correct. Actually i added the caption (subtitles) as the correction for checking all neighbors (might take time to reflect)
Apologies to have missed it but i really hope the intuition was clear 😇❤️🙏
Thank you
Thank you Rajat for watching 😇❤️🙏
Great Explanation !! Do you think that doind the daily challenge everyday consistently would help improve the problem solving skills ?
Congratulations bhaiya🎉🎉🎉 for 9k , you deserves millions❤❤❤
Means a lot 😇🙏
Your videos are superb, My placement is near and covering all videos of all playlists is a long process, can you please make a of very imp. and frequently asked questions? Also it would be very great if for each question in the sheet we have a link to your video.
I know there are lots of sheets available but , I only trust you , please consider this request, it will help a lot to all students.
In java code, why we take 2D array for visited. Why cant we take Set visited?
Yep you can.
I just tried to show two different ways to use visited 😇❤️
iss question ko kl re-attempt krunga bahott hi jyada achha question h 1 baar me samajh me nhi aaya
Sure thing ❤️
great explanation sir soo helptul tq
Thank you so much for watching ❤️❤️
Also, If you think I should create a separate video in which I should do a complete dry run for the video, then let me know, i will make one for sure ❤️❤️❤️
yess sir if you have time then make a complete video for dry run .i understood and tried to write the code but got a bit confused ,@@codestorywithMIK
finally 17/30
Contest k solutions bhi provide kro bhai please
Nobody would come up with a solution , if they have not seen such problems.
Hi Mik, Thankyou for the clear explanation. Awesome Video! as always.
i have one question, what is the need of bit masking? i mean cant we simply use a 2d array which tracks the state of (parent, child) i.e if i am coming from 0th node and going to 1st node then i will simply set it as isvisited[0][1] = true.
next time, when i come in this same situation i.e 0 to 1, i can simply check if isvisited[0][1] = true or not.
Hi Ayush,
That’s such an IMPORTANT qn you asked.
Actually i took a very small example.
In big examples- the repeated path can be large as well
For example : you came to 3 via 0,1,2
Path - 0 -> 1 -> 2 -> 3
Suppose you came to 3 via 0,4,2,3
Here if you notice, you came to 3 from 2 but the entire path is different.
Hence keeping track of only previous node will not be enough, we need entire trail path to see if we have seen the path before or not.
Hope this answers your qn.
And thank you so much for your precious comments ❤️❤️❤️
@@codestorywithMIK thanks for the answer. i was wondering the same thing
@@codestorywithMIK Thanks a lot for this. And good Qn bhai
@@codestorywithMIK thanks for your response, I will dry run few scenarios to see where it fails.
Sure Ayush.
Just simply write the code as you explained. Then any test case failing will be caught. 😇❤️
thank you so much sir♥
Thank you so much for watching ❤️❤️
Also, If you think I should create a separate video in which I should do a complete dry run for the video, then let me know, i will make one for sure ❤️❤️❤️
@@codestorywithMIK no sir I will try from myself ♥️
@shivamtomar9658 sure 😇🙏❤️
Kaafi hard problem tha aaj ka, pr concepts clear hogye kaafi
Glad to hear that my video helped ❤️❤️❤️
Also, If you think I should create a separate video in which I should do a complete dry run for the video, then let me know, i will make one for sure ❤️❤️❤️
Bhaiya give us the chance to do some hard work too :) @@codestorywithMIK
thanksssssssssssssss
Thank you 😇
wow🎩📴
Thank you so much 🙏😇❤️
I was trying to use normal DFS here, what I was doing was I will check everynode as the starting node to get the minimum.
In dfs function I am checking all the nodes I can travel, once I make a dfs call to that node, I remove that edge from the graph and after I calculate the ans. I add this edge back to the graph.
But I am not getting the optimal ans. Can someone help me?
For getting shortest path, DFS can never give you optimal path.
Always remember that shortest path can only be found using BFS.
DFS never guarantees shortest path
@@codestorywithMIK Thanks broo
30:55 when we pop the first element {0,1} Why we do not push {2,5} and {3,9} along with {1,3}. 0 has 3 three neighbours 1,2 and 3 why do we only push {1,3} in the queue and move to {1,2}.
Yes yes, my bad they should have been added too. But i covered adding the neighbors further in the video. I hope that cleared the confusion.
But please let me know, if you guys need a separate FULL DRY RUN video on this, kindly let me know, i will make one for sure 🙏😇
thank you so much for replying and clearing my doubt. I gave a lot of time to it and then finally decided to write a comment. make a full dry run video, if manageable and add its reference to the title/pinned comment/description of the video.@@codestorywithMIK
Bhaiya in first iteration 0 had 3 choices right?
MIK it was as smooth as it could be ❤
Thank you so much Sachin ❤️
please let me know, if you guys need a separate FULL DRY RUN video on this, kindly let me know, i will make one for sure 🙏😇
@@codestorywithMIK it's okay MIK I think u need not to do the full dry because if we work hard more than u then only it will benefit us 🙂
@@codestorywithMIK mik one doubt why we are using the while loop while(n--){--} for that n chunk processing what if we don't do that ??
@sachinmohanty4577 If you remember I mentioned that we have to start BFS from all nodes at once.
If we don’t start BFS from all nodes at a chunk (level) at once, then we will never get shortest path guarantee.
Starting BFS once for a chunk ensures that we are starting BFS from all nodes at once.
I will suggest you to do a dry run in a small example and try doing BFS one by one instead of chunk by chunk.
@@codestorywithMIK so basically nested bfs right??
Sir, Will you reveal your face when you receive Silver Button ? 😃
and bhaiya isme hmne visited ko set me kyun store kiya h vector me kyun nhi
You can use vector also.
See my Github link in the description.
I have provided both - using 2-D array for memoization (in Java code) and using set in C++
@@codestorywithMIK ohh , hmm set tabhi use krte h jbb hmme duplicate element nhi chahiye hotte h na
Bhaiya can we use unordered set?
C++ doesn’t allow to use pair inside unordered set. That’s why you will have to use ordered set only ❤️😇
@@codestorywithMIK thanks bhaiya for this explanation
just silly mistake, the mask for 0 is 0000 35:27
Hi there,
Mask for 0 will be - 0001
Because from 0 it means that 0th bit will be set i.e. we will do (1 (0001)
I hope that clears 😇❤️🙏
Thank you so much for watching
why we didn't make adj list 🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔
bro where have you been
Hi there, actually 15th Sept and 16th sept POTD videos were already present in my playlist -
15th Sept POTD -
Using Prim’s - czcams.com/video/hsr7KolYDH0/video.htmlsi=fqkY9yq7s42MhvR_
Using Kruskal’s - czcams.com/video/O6wQQtv71S0/video.htmlsi=bJXhfRIhjiXQ49eq
16th Sept POTD -
czcams.com/video/QIu9HeyEjPc/video.htmlsi=N7C15PELOKP0UjDS
Hope that helps 😇🙏❤️
@@codestorywithMIK oh i thought u might have got sick so no videos 🙂
time complexity?
Time Complexity : 0(2^N * N^2).
Notice the while loop that performs the BFS traversal of the graph.
In the worst case, the while loop can run 2^N iterations, where N is the number of nodes in the graph. This is because the program explores all possible combinations of nodes using bit masking i.e. each bit can be either 0 or 1 (2 possibilities) --> 2^N
Within each iteration, there is a nested loop that iterates through the neighbors of the current node. In the worst case, this inner loop iterates N times for each node.
So, the overall time complexity is 0(2^N * N^2).
yeah got it one more question the type of bfs you used in the question isn't same as multisource bfs??
@@codestorywithMIK
hi bhaiya. Aaj aapse ek general question puchna tha.
i have some friends who are taking online one-to-one coaching. It is giving me a feeling of lagging behind. I don't think i would be needing any of those coz i have you as my mentor and i have already gone through all the data stuctures. Please guide me how to deal with this situation i am stuck 😔😔.
My current strategy (my daily routine)
1) I make sure to solve atleast 5 problems
2) I understand the question from your video and give myself 1/2 hr -1hr on the approach
3) If i dont get it i watch the solution save it to my weekly-repeat list and move ahead
4) Resolve it on a span of 5 days then move it to the monthly repeat section
5) I give all contests only on leetcode
6)Upsolve the question on the next day.
Struggling
1) I did 60 question on graph then lost touch. Now i know the concepts but i forget some of the details.
This is what i do daily. I am able to code 30-40% of the questions you do. Is this the right path?Please suggest
Wow. First of all, “weekly-repeat list”,
Very rare people do this. But this will be very fruitful in long run. You just never stop this. This is a very good way of revision.
See, it you are consistent and following the path you showed above, then with time you will keep growing and you will definitely don’t need anyone for help.
Please never stop giving contests, its a Gem .
Also, if you forget concepts of Graph, not to worry, you can revisit them in your free times.
Always remember, even dope coders of Korea, China etc. also forget concepts, they also have to revise timely and they also struggle in some qns. But they keep the practice consistent, and that’s what I want to tell you, be consistent with this strategy and never stop this.
Trust me, give it some time and you will definitely see change in you.
@@codestorywithMIK thank you as always for guiding me
@dhairyachauhan6622 Happy to help.
But I am really impressed that you keep a weekly revision list. Blows my mind 👍🏻👍🏻👌👌
I also have a list where I keep Problems for revising again after 5-10 days.
But I often break this routine. Being consistent is tougher than studying DSA I believe. But this channel has helped me a lot to regain my consistency. Hope to be on this path for long until I crack a good company.
36:33 bhaiya yha pr aapne 0011 OR 0010 = 0011 galat likha h
Hi Abhay, OR of 0011 and 0010 will be (0011) only.
Can you please confirm if this is what you are referring to ? ❤️
@@codestorywithMIK sorry bhaiya mai confuse ho gya tha maine se socha tha
Ye kaun sa operation hai bss ye btao do
0011 OR 0010 = 0101
@Abhay14 This is actually OR operation.
If you remember, OR operation is done like this :
1 OR 0 = 1
1 OR 1 = 1
0 OR 1 = 1
0 OR 0 = 0
Hope this helps 😇
Sir take oa questions also not just leetcode ones🫠🫠...
Soon 😇❤️