Course Schedule II
Explore how to use topological sort to solve course scheduling problems involving prerequisites. Learn to identify valid course sequences or detect cycles that make completion impossible. This lesson guides you through defining the problem and practicing your solution in code.
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?
Select all that apply.
n = 7
prerequisites = [[1, 0], [1, 2], [2, 3], [3, 4], [4, 5]] 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 java.util.*;class CourseSchedule{public static List <Integer> findOrder(int n, int[][] prerequisites) {// Replace this placeholder return statement with your codereturn new ArrayList<>();}}