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 nn courses labeled from 00 to n−1n-1. Some courses may have prerequisites. A list of prerequisites is specified such that if Prerequisitesi=a,bPrerequisites_i = {a, b}, you must take course bb before course aa.

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

Constraints:

Let nn be the number of courses.

  • 1≤n≤15001 \leq n \leq 1500
  • 0≤0 \leq prerequisites.length ≤1000\leq 1000
  • prerequisites[i].length ==2== 2
  • 0≤a, b<n0 \leq a, \space b < n
  • a≠ba \neq b
  • All the pairs [a, b][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(n2)O(n^2), where nn is the number of courses. However, the space complexity of this naive approach is O(n)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 80+ hands-on prep courses.