leetExpert
Practice

Course Schedule II

Module 23 · Graphs

Problem

Same setup as Course Schedule: numCourses courses and a list of prerequisite pairs [a, b] meaning "b before a." Return any valid order in which to take all the courses, or an empty array if no valid order exists (a cycle makes it impossible). (LeetCode 210.)

Examples

Example 1

InputnumCourses = 2, prerequisites = [[1,0]]Output[0,1]

Example 2

InputnumCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]Output[0,1,2,3]

Explanation. or [0,2,1,3]

Example 3

InputnumCourses = 1, prerequisites = []Output[0]

Constraints

up to 2000 courses, up to 5000 prerequisite pairs.

Attempt it first

This is Course Schedule with one change: instead of a boolean, return the order itself. Before opening anything, revisit your Course Schedule solution (or the Topological Sort concept lesson directly) and identify exactly which variable in Kahn's algorithm already contains — as a side effect of its normal operation — precisely the sequence this problem asks for.