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 n1n-1. Some courses may have prerequisites. An array 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 an array 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 n1n-1 range with no prerequisites.

Constraints:

Let nn be the number of courses.

  • 1n15001 \leq n \leq 1500
  • 00 \leq prerequisites.length 1000\leq 1000
  • prerequisites[i].length ==2== 2
  • 0a, b<n0 \leq a, \space b < n
  • aba \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 array, 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 array of the courses’ prerequisites. Using the given array 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.