Topological sort | Course schedule 2 | Leetcode

This video explains a very important programming interview concept which is based on graph algorithm and is known as topological sort.This is a very important concept for solving graph problems based on ordering.We can find the topological sort using the simple DFS along with a STACK.Topological sort for a graph is only possible if it is a directed acyclic graph (DAG).I have explained the entire algorithm by taking proper examples and have also shown the code implementation using a problem course schedule 2 which is from leetcode #210.I have shown the code walk through at the end of the video.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
========================================================================
INSTAGRAM : / surya.pratap.k
SUPPORT OUR WORK: / techdose
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithT...
TELEGRAM Group LINK: t.me/joinchat/...
=======================================================================
CODE LINK: gist.github.co...
USEFUL VIDEOs:-
Course Schedule: • Course Schedule | Dead...
DFS: • Depth first search | D...

[@codestorywithMIK]

You teach a topic and then you solve a question based on that topic. This is the best approach of teaching. Thanks

[@techdose4u]

Welcome

[@neghatnazir1668]

@@techdose4u hey i am a bit confused would you pls clear it? if we start at node 4 the order comes out to b 5 3 0 4 1 2 which is not correct i guess? would pls explain this to me i am not getting it?

[@willturner3440]

@@neghatnazir1668 you are correct

[@sreesayihrudai9541]

@@neghatnazir1668 Try to run a loop from starting vertex to end vertex you will get the answer

[@manishkumar-qn6lx]

​@@techdose4u Even if there exists a loop, still there is the possibility to cover all the courses. Ex. [[0,1], [2,0], [2,1], [3,1], [3,2]]. ( [0, 1], indicates that to take course 0 you have to first take course 1 ) In the above example, there exists a loop but still, we can complete all the courses in the following order : [0,2,1,3].

[@JayDonga]

Great video, thank you for clear explanation. One addition here, instead of doing double work (pushing elements to stack and popping every element to get answer), you can add each new element on front of LinkedList and then return the LinkedList.

[@amith1989]

Quick, crisp and clear!! Fantastic way of explaining Topological sorting in 13 minutes.!

[@techdose4u]

Thanks

[@harshbhadoria7200]

The day before yesterday I came to youtube for a solution to a question, as usual, randomly I picked your video. I don't know what happened after that day, whenever I search for the question on youtube I'm writing Techdose at the end. Conclusion: The way you teach and make us understand every topic is too good.

[@techdose4u]

Thanks 😊

[@sainathy9225]

@techdose, you are doing great job . I used to follow nich white and Kevin naughton . Now iam waiting for your videos. Keep doing!

[@techdose4u]

Thanks :)

[@bostonlights2749]

Same for me as well

[@vman049]

Same. @techdose completely dominates them!

[@greymatters22]

Thank you so much this channel, this channel focusses on solving all difficult problems based on advanced concepts. Love it

[@noobninja4882]

perfect explanation sir, thanks a lot , following your graph series from the beginning , please continue this as i am learning a lot from this, and graph is my biggest fear

[@techdose4u]

Okay sure.

[@sakshamgupta2740]

graph videos are a real delight. Thanks for the content

[@techdose4u]

Welcome:)

[@joydeepbhattacharjee5305]

one of the best channel for CS in youtube...thank u so much for such awesome contents... and keep helping us like this..

[@techdose4u]

Sure. Thanks :)

[@MarioFernandez-hx1cm]

in three hours ive got my last exam at my carrer as engeneer, and this helped a lot. Hopepefully ill aprove, thanks a lot

[@kailashjangir1530]

what if in starting we goes to node 3 rather than going to 2 in dfs, then answer would be changed na?

[@shridharsarraf2188]

This is best playlist on KZbin to learn Graphs ❤❤❤❤

[@techdose4u]

Thanks ☺️

[@JohnWick-kh7ow]

Using recursion- bool isCyclic(vector adj[],vector& vis,vector& order,int curr){ if(vis[curr]==0){ return true; } if(vis[curr]==-1){ vis[curr]=0; for(auto e:adj[curr]){ if(isCyclic(adj,vis,order,e)){ return true; } } order.push_back(curr); vis[curr]=1; } return false; } vector findOrder(int numCourses, vector& prerequisites) { vector adj[numCourses]; vector vis(numCourses,-1); vector order; for(int i=0;i

[@poojanshah9302]

Very thorough explanation. I am always looking for your explanation before solving any Leetcode problem.

[@techdose4u]

Great :)

[@mwshubham]

How could something be such easy. Thanks 😊🙏

[@techdose4u]

Welcome 😊

[@shivammaniharsahu1228]

really good one keep sharing such vedios

[@akm1237]

Hello sir. Does it matter which edge we start with for the topological sort? Say we begin with 3, wouldn't 3 come before 2 in the stack?

[@aparnamittal8653]

No, it does not matter. 3 will come before 2 in stack but when we pop elements, it will result in coming at end in the order which is correct.

[@shashanksinha6966]

there is an extra recursive call to check cycle , we can do it using bfs in less time complexity

[@techdose4u]

👍🏼

[@pcccmn]

This approach is accepted by LC. Naturally because of the method `detectCycle`, the solution is beaten by many who got it done within 1 dfs method..But honestly, this solution should be taught first before attempting NeetCode's. This solution is way simpler to understand and implement!

[@shagunlamba6481]

great explanation, recommending to everyone

[@techdose4u]

Thanks :)

[@anmolwadali9227]

gud explanation !! Plz Make videos on Minium spanning tree kruskal & prims algo

[@techdose4u]

It will eventually come. Making videos topicwise in order.

[@galeforceonline3847]

Thanks. its good that you explain the subject using pseudo code aswell.

[@techdose4u]

Welcome

[@AyushPandey0]

Excellent explanation sir, keep uploading more videos on graph problem.

[@techdose4u]

Thanks

[@agileprogramming7463]

Wonderfully explained as always!

[@techdose4u]

Thanks agile :)

[@shaziasamreen8584]

Excellent Explanation..... Please upload leetcode daily challenge questions also..Your videos were very helpful..

[@techdose4u]

Thanks :)

[@josevalbuena9423]

Why is the motivation to perform Khan’s algorithm/Topological Sort with a DFS approach to solve this problem while in the explanation of the topic is based of BFS? What’s the reason? Can both approaches be used to apply Topological sort?

[@fadiahetrakeshkumar9454]

Nice video Best video for kahn algorithm

[@techdose4u]

Thanks

[@vishal40007]

I didn't think of using the stack. What is the thought process for solving the problem? How did you come up with stack?

[@manishkumar-qn6lx]

​ @TECH DOSE Even if there exists a loop, still there is the possibility to cover all the courses. Ex. [[0,1], [2,0], [2,1], [3,1], [3,2]]. ( [0, 1], indicates that to take course 0 you have to first take course 1 ) In the above example, there exists a loop but still, we can complete all the courses in the following order : [0,2,1,3].

[@techdose4u]

There is no cycle in your graph :)

[@afnaanrafique366]

Why is simple BFS not a solution to this problem?

[@ameynaik2743]

Nice video. How did you find cycles in the graph?

[@Sportamrina]

watch the course schedule video - it checks for cycles in the graph

[@yihongliu3850]

really nice and clear

[@techdose4u]

Thanks Yihong :)

[@smartwork7098]

Great work, man!

[@tech_wizard9315]

1) m a fresher, working in IT company of Jodhpur(9 hours job). If I prep DSA with c++ , 3-4 hrs each day for 3 months(leetcode) , can I gt job at Google,FB, Apple ? If not, then hw much time/months need? 2) If.i have one project in my resume, is it enuf for project round of FAANG

[@techdose4u]

You can crack job at AMAZON , Microsoft with this preparation but Google and apple requires you to distinguish yourself from the rest. Your resume should show what sets you apart from the rest. This prep is done by thousands of jobseekers and hence you need either an exceptional coding profile or an exceptional dev profile or both in a balanced way.

[@tech_wizard9315]

@@techdose4u is one project enuf?

[@ManojKumar-so9kw]

@@tech_wizard9315 nope man it wont be enough at any day for any of the product based companies

[@techdose4u]

@@tech_wizard9315 one project is enough but it depends on what work you had done, the complexity and level of responsibility you were handling and the amount of effort you put. This defines your character as an SDE. Don't worry if you have 1 project, but the important thing is your dedication alongwith complexity and level of ownership of your project.

[@exodus5948]

Bro , I am in a same situation 2020 batch and more from electronics batch from a tier 3 college, But I suggest you must make 2-3 Projects, OtherWise interviewer is definitely going to grill a lot. Best of luck for your preparations.

[@mr_tpk]

Awesome 🔥🔥🔥

[@AmanGupta-ud6sy]

Amazing video.....best explanation.

[@techdose4u]

Thanks

[@pranjalgupta9427]

Very nice explanation 👍👏😊

[@techdose4u]

Thanks

[@nayanjain5761]

In 1st video CS-I (Course schedule I) you created ajd by adj[i[0]].push_back(i[1]); i.e. 0->1 , and here inverse adj[i[1]].push_back(i[0]); 1->0. Also I checked for CS-I adj[i[1]].push_back(i[0]); is also passing, please explain. Thanks

[@techdose4u]

If you are checking cycle then it doesn't matter how you take. It should be same for all the edges

[@nayanjain5761]

@@techdose4u Thanks for this quick response and and all amazing content.

[@kiranathavanad8050]

good one

[@electric336]

Very helpful video. You explained it very well.

[@arindamchakraborty5880]

@TECH DOSE I am having one doubt, Can we write 0 before 4 in the top sort? like 5, 0, 4 likewise? Please clarify.

[@supratikk]

I have implemented the same algo but just used the cycle detection method shown by you in the "course schedule1" problem. But its giving me a time Limit Exceeding error. Is that the reason why you slightly tweaked the cycle detention method in this problem?

[@techdose4u]

I don't exactly remember the reason 😅

[@vidyakore3930]

thanks a lott, explained so nicely... keep making such videos!!

[@techdose4u]

Thanks

[@mohammadshafihamidi1778]

if its possible i need some application of topological sort in field of providing accessibility in organic areas

[@i_mchick5311]

Hello sir ! can u also share the notes that u write while teaching ??

[@cristianandrei811]

great video

[@gaurangmittal5563]

Sir why did u used a graph coloring method for a detecting cycle in a directed graph, as in your vidoe you have used another approach.

[@techdose4u]

Graph Coloring is simple and works in O(V+E) otherwise we will have to use stack.

[@harshithg5455]

Super video! I applauded for ₹200.00 👏👏👏

[@techdose4u]

Thanks for supporting ❤️

[@harshithg5455]

@@techdose4u Thank you for the remarkable videos 😀

[@techdose4u]

Welcome :)

[@ashishg656]

Great content :)

[@learnfromramayan8176]

sir why cant we push the processed node and return answer following the exact method you taught in course schedule i. when we make a course processed=1 at that time why cant we push and add to result? Thank you in advance

[@superneutral1663]

brilliant explanations,love all your videos

[@swagatpatra2139]

What about loops in the schedule? We need to return an empty array in that case.

[@be_like__prateek]

U r just awesome 💕

[@techdose4u]

Thanks :)

[@davngo]

Your explanations and solutions are so beautiful.

[@techdose4u]

Thanks

[@prasannakumarz]

very good explanation

[@techdose4u]

Thanks

[@AmarKumar-vo2bv]

Please make video on finding articulation point

[@techdose4u]

It will come in connectivity topic. I am covering topicwise. Have patience.

[@willturner3440]

Thanks sir for such a great explanation, genius 🥰

[@techdose4u]

Welcome :)

[@rajatgarg6859]

It was amazing ,thanks buddy :)

[@iSumitYadav]

TopoSort and Cycle finding can be combined to a single function only

[@techdose4u]

I separated to provide code for topological sort.

[@iSumitYadav]

@@techdose4u oh okay...👍🏻

[@vinitraj6268]

At 4:29 you started from node 0.....but I think we can start from any node....

[@umapathybabu8397]

After graph series, can you start with greedy

[@techdose4u]

I will try.

[@shivam.priyam]

what if we add two more edge (5 -> 6) and (6 -> 2)

[@rahulchudasama9363]

Awesome explaination, One suggestion Topological sort explaination video should come before the Reconstruct Itinerary video. So that flow can be maintained.

[@techdose4u]

Okay i will reorder. Thanks for letting us know.

[@ShubhamKumar-zy7wy]

Bhagwan hai bhai ye

[@techdose4u]

😅

[@abhishekkumardwivedi3817]

sir, please try to add a video for egg dropping puzzle if possible

[@GAURAVKUMAR-uj3to]

Can these orders be the right order or not? 5, 0, 4, 2, 3, 1 5, 0, 3, 4, 2, 1 5, 0, 3, 4, 1, 2 please explain.

[@sahilpradhan877]

no, because 0 has indegree of 1 and 4 has indegree of 0, so 4 should come before 0

[@exodus5948]

I think within few months you are going to join google. :D, Loved your intuition behind problems. Please also make videos on Greed Approach

[@techdose4u]

After graphs I am planning on doing DP + GREEDY mixed :)

[@AmarKumar-vo2bv]

Articulation point

[@techdose4u]

Have patience bro

[@lokeshpatel3914]

what if we get more than one components in graph and 1 component forms DAG and other does not ?

[@AjayKumar-un2fz]

Simply , we can't do topological sort because one of component is not DAG . We will got stuck in cycle while selecting courses for that component.

[@lokeshpatel3914]

@@AjayKumar-un2fz But in such case an empty array can't be returned as output coz there must be some courses we can take as valid courses which forms different component .

[@techdose4u]

Read this: stackoverflow.com/questions/36712146/if-topological-sort-uses-dfs-how-can-it-succeed-on-disconnected-graphs

[@programmingstuff5741]

Bro please explain Leetcode Island Parameter problem

[@starc701]

course schedule 3 please

[@techdose4u]

Later

[@starc701]

@@techdose4u ya i did it, but thanks

[@techdose4u]

👍

[@nagarjunreddygaddam5059]

Hello Sir, In your previous videos, you showed graph coloring is used to find a cycle in an undirected graph and a different technique for a directed graph. Here you have used graph coloring to find a cycle in the directed graph. Is the graph coloring algorithm different between directed and undirected graphs? Video link for directed graph - kzbin.info/www/bejne/ZpWtnoergteIkK8 Video link for undirected graph - kzbin.info/www/bejne/gmGnlJiGmrx7pK8

[@In5Minutes2294]

same doubt naggu

[@bharadwajachepuri968]

Hello Sir....I wanted to support ur work, plz try to add a BHIM UPI gateway payment

[@bharadwajachepuri968]

@patreon

[@techdose4u]

Patreon only has paypal and credit card options. I will be adding channel membership soon in a couple of days. You can join there and take extra benefits.

[@sarthakgupta1263]

dfs + stack == mindblown;/

[@techdose4u]

😁

[@ishitamundhra8572]

TIP : watch at 2× speed

[@techdose4u]

😅 it's that slow !!

[@ishitamundhra8572]

@@techdose4u I guess 😂 But really useful thanks !

[@techdose4u]

@@ishitamundhra8572 :P

[@amitavamozumder73]

in 4:00 if I start from node 3, then the order will get messed up, right?

[@sharadmaheshwari5319]

your explanations goes smoothly in my mind, thanks for help !

[@techdose4u]

Welcome :)

[@bostonlights2749]

Quality content every time

[@techdose4u]

😁

[@rakeshsahni_]

This video Clear all my doubts regarding topological sort, thank you sir

[@pranjalgupta9427]

Can i also start from other vertex rather than 0?

[@thiyagarajanr225]

Content at its best! How much hours did you spend in making the videos bro? Efforts behind the scenes matters a lot! Usually i dont comment in any videos, but i used to comment to value your efforts 💖

[@spetsnaz_2]

Such simple and elegant explanation can only be expected on TECH DOSE🍺

[@techdose4u]

😁

[@neerajpant4071]

last few seconds was awesome it's more like listening to an terms and conditions for an insurance policy 🤣😄

[@techdose4u]

😅 I just want to wrap the unnecessary talks quickly 😅

[@neerajpant4071]

@@techdose4u hehehe..correct Nice explanation. Always worth watching your videos.👍

[@techdose4u]

Thanks.

[@manmeetsingh4272]

In the given example, from node 0 you first traversed to 2 then to 3 so the stack will be { 2, 1, 3, 0, ....} but if we traversed node 3 first before 2 then the stack will be { 1, 3, 2, 0, ....} as we see the stack is not in topological order. Because when we run our program in pc we don't know what node will be traversed first. Can you explain this case?

[@gontlakowshik2345]

Sir, can you explain how find cycle in a graph

[@spetsnaz_2]

Already explained for directed and undirected graph... Check his Graph playlist

[@sohamshinde1258]

Best in class channel with the best in class explanation. Thankyou so much.

[@techdose4u]

Welcome :)

[@codebits2120]

Thanks 😊

[@techdose4u]

Welcome

[@deepakjoshi4374]

I solved this Course Schedule I/II QS using the concept of Detect Cycle in a Graph (Using Colour Method). If there is a cycle you will not be able to complete the courses. else you can always take all the courses. For printing the courses, you can put into an array when you visited all its descendants.

[@Cat-uk2jx]

Hello! I was doing this exercise I started with 4to 2 then I went to 4to 1. I then restarted at 5 to 0 to 3 and I got the following result 5,0,3,4,1,2. Is this correct? I read that one can start with any node (not just 5 or 4). Also I saw another comment with I different topological ordering which I also got 5,0,3,4,2,1. Can anyone explain why these are wrong? I am a beginner and I am having some difficulty grasping this concept. Thank you!

[@shubhamagarwal2998]

7:43 this is not 100% necessary that nodes with outgoing degree=0 is comes at last .... like if in this example 0->{2,3) dfs(0)->dfs(3)->dfs(1) o/p stack = [1,3 dfs(0)->dfs(2) o/p stack = [1,3,2

[@sheldon9415]

Such a good and clear explanation ! Thank you for the time you put in making this awesome video!

[@techdose4u]

Welcome :)

[@ekinkale6243]

ı think this is wrong because 2 has 3 indegree inputs (not 2 indegrees). that's why when we delete the 4 and 5 , it has also 0 indegree input. so it should be 4 possible results : " 4 - 5 - 0 - 2 - 3 - 1" or " 4 - 5 - 0 - 3 - 2 - 1" / " 5 - 4 - 0 - 2 - 3 - 1" or " 5 - 4 - 0 - 3 - 2 - 1"

[@jineshdave6451]

Best explanation ✨✨

[@techdose4u]

Thanks :)

[@taskmaster4824]

buddy it is showing TLE in graph coloring ??

[@mayankpatel6735]

Bhai tabiyat sahi rakho aur videos banate raho, katai aag ho aap

[@anumonto]

simple and clear explanation.. Great!.

[@techdose4u]

Thanks

[@iampatelajeet]

Amazing way of teaching bro, loved it.. Keep it up. Thanks!

[@techdose4u]

Thanks ☺️

[@shreyasbhujbal8777]

baap!

[@pradnyabapat9531]

Thank you!!

[@hiranyam]

beautiful!