Solution: Course Schedule II
Let's solve the Course Schedule II problem using the Topological Sort pattern.
Statement
Let’s assume that there are a total of courses labeled from to . Some courses may have prerequisites. A list of prerequisites is specified such that if , you must take course before course .
Given the total number of courses and a list of the prerequisite pairs, return the course order a student should take to finish all of the courses. If there are multiple valid orderings of courses, then the return any one of them.
Note: There can be a course in the to range with no prerequisites.
Constraints:
Let be the number of courses.
-
prerequisites.length
prerequisites[i].length
- All the pairs are distinct.
Solution
So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.
Naive approach
The naive approach is to use nested loops to iterate over the prerequisites list, find the dependency of one course on another, and store them in a separate array.
The time complexity of this naive approach is , where is the number of courses. However, the space complexity of this naive approach is . Let’s see if we can use the topological sort pattern to reduce the time complexity of our solution.
Optimized approach using topological sort
This problem can be solved using the topological sort pattern. Topological sort is used to find a linear ordering of elements that depend on or prioritize each other. For example, if A depends on B or if B has priority over A, B is listed before A in topological order.
For this problem, we find the topological order of the given number of courses using the list of the courses’ prerequisites. Using the given list of prerequisites, we can build the graph representing the dependency of one course on another. To traverse a graph, we can use breadth-first search to find the courses’ order.
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.