# Solution: Course Schedule II

Let's solve the Course Schedule II problem using the Topological Sort pattern.

We'll cover the following

## 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.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.