LeetCode 207 & 210: Course Schedule I & II | Topological Sort | Kahn's algorithm - Interview Ep 78

This is a very popular, practical algorithm which could be used in quite a few places.

⭐ Support my channel and connect with me:

Problem link on LeetCode:

Algorithm explained:
we first find a set of vertices that don't have any incoming edges;
then we loop through these vertices to remove any edges using them as incoming vertices;
along the way, if we find other vertices don't have any incoming edges any more, we'll add them into this set as well;
until this set becomes empty, we break out of this loop;
then we check if there are still any edges there, if so, this is a DAG (Directed Acyclic Graph), it's impossible to find such a topological ordering.
Otherwise, return the order.

Time complexity: O(V+E) (V is the number of vertices and E is the number of edges in the given graph)

// TOOLS THAT I USE:

// MY FAVORITE BOOKS:

My ENTIRE Programming Equipment and Computer Science Bookshelf:

And make sure you subscribe to my channel!

Your comments/thoughts/questions/advice will be greatly appreciated!

#Kahnsalgorithm #graphsearch #topologicalsorting #softwareengineering #leetcode #algorithms #coding #interview #SDE #SWE #SiliconValley #programming #datastructures

[Sasha-fbvb]

Best explanation I've ever seen ♥️

[Mauglus]

Love your algorithm explanations! Keep it going :)

[shauryabavishi]

It is really helpful video, explained in easy manner!

[GorgeousPuree]

Great explanation, I rewatched this video few times to finally understand this algo...
Wouldn't it be more efficient to create topoMap and instead of iterating through every prerequisite in the while loop, iterate only through courses that are children of the currently iterated course?

[warzone]

thanks, clear explanation and slides.

[harshavardhanm]

thank you so much, very clearly explained

[Themerp]

Good video, just wish it was edited to make it shorter, perhaps by cutting out some of the example explanations such as at 2:30 and 4:47. The video just drags at these points. Also adding some timestamps to the video for the various sections would help people quickly navigate to the part of the video they care about.

[toekneema]

Great explanation!
I have one question though, can you describe a situation when there will be left over indegrees: I don't really understand when that will ever happen. Seems like as long as it's not a cycle, all the edges should be able to be visited so all the indegrees would be 0 at the end

[nimanizky]

Great tutorial, You should do thia tutorial for another algo such as dp or backtracking

[rydmerlin]

Is it significant to get the iterator every time thru the while?

[RohitSharma-jiqh]

is it ideal to store courses indegree in array when constraint for courses are 10^5. In worst case, we need to store 10^5 courses indegrees.