Solution: Course Schedule II

Statement

Let’s assume that there are a total of $n$ courses labeled from $0$ to $n-1$. Some courses may have prerequisites. A list of prerequisites is specified such that if $Prerequisites_i = {a, b}$, you must take course $b$ before course $a$.

Given the total number of courses $n$ 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 $0$ to $n-1$ range with no prerequisites.

Constraints:

Let $n$ be the number of courses.

• $1 \leq n \leq 1500$
• $0 \leq$ prerequisites.length $\leq 1000$
• prerequisites[i].length $== 2$
• $0 \leq a, \space b < n$
• $a \neq b$
• All the pairs $[a, \space b]$ 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 $O(n^2)$, where $n$ is the number of courses. However, the space complexity of this naive approach is $O(n)$. 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.