Course Schedule II
Understand how to apply topological sort to find a valid sequence for completing courses given prerequisite constraints. This lesson teaches you to identify cycles that prevent course completion and implement solutions that return possible course orderings or indicate impossibility.
We'll cover the following...
Statement
You are given n courses, labeled from 0 to n - 1. Some courses have prerequisites, which are provided as a list of pairs: prerequisites[i]
Your task is to determine a valid order in which you can complete all the courses and return it as an array of course labels.
If there are multiple valid orderings, you can return any of them.
If it’s impossible to finish all courses (due to a cycle in prerequisites), return an empty array.
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.
Examples
Understand the problem
Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:
Course Schedule II
What is the course order if the following list of prerequisites and an integer n are given as input?
n = 7
prerequisites = [[1, 0], [1, 2], [2, 3], [3, 4], [4, 5]]
Select all that apply. Multi-select
[1, 0, 2, 3, 4, 5, 6]
[0, 2, 1, 6, 5, 4, 3]
[0, 5, 6, 4, 3, 2, 1]
[6, 5, 4, 3, 2, 0, 1]
Figure it out!
We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.
Try it yourself
Implement your solution in the following coding playground:
import Queue from './queue.js'export function findOrder(n, prerequisites) {// Replace this placeholder return statement with your codereturn []}