Course Schedule II

Medium · Graphs

You need to complete a set of numbered courses labeled 0 to n-1. You are given a list of prerequisite pairs where each pair [a, b] means you must finish course b before course a. Return one valid order in which all courses can be completed, or an empty list if no valid order exists because of a cycle of dependencies.

Examples

Input:  numCourses = 2, prerequisites = [[1,0]]
Output: [0, 1]
Why:    Course 0 has no prerequisite and course 1 needs course 0 first, so 0 must come before 1.

Input:  numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0, 1, 2, 3]
Why:    0 has no prerequisites, 1 and 2 both need 0, and 3 needs both 1 and 2, giving this ordering as one valid completion order.

Input:  numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: []
Why:    Course 0 needs course 1 and course 1 needs course 0, forming a cycle that makes completion impossible.

Constraints

1 <= numCourses <= 2000, 0 <= prerequisites.length <= 5000, prerequisites[i].length == 2, no duplicate pairs

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Course Schedule II

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Course Schedule II. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.