Topological sorting – An essential algorithm for interview coding | by SHIVAM JINDAL | January 2025

Too big to read? Watch it on YouTube

When we schedule jobs or tasks, they may have dependencies. For example, before completing task 4 we need to complete 5 and 0 first (in the image above). In this case, given a set of tasks and their dependencies, how can we organize our schedules? There is an interesting graphical algorithm: Topological sorting.

My article is free for everyone. If you don’t have an active subscription, you can read it here. Otherwise, please continue 😉

In simple words, it helps you determine the order in which you should complete a set of related tasks, ensuring that you do not start a task until all of its prerequisites or dependencies are met.

It’s like make sure You can’t make a cake until you have all the necessary ingredients and utensils ready, one step at a time. Topological sorting is widely used in project planning, building software with dependencies, etc.

According to Introduction to Algorithms, given a directed acyclic graph (DAG)a topological sort is a linear order of all vertices such that for any edge (u, v), u comes before v. Another way to describe it is that when you put all the vertices…