Course Schedule II

Medium

Topological Sort

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

This builds on Course Schedule I by requiring you to actually produce a valid ordering, not just detect if one exists.

Real-world analogy: Imagine a build system where packages have dependencies. This problem is equivalent to determining the order in which packages should be compiled so that every package is built after all its dependencies.

Example 1

Input: numCourses = 2, prerequisites = [[1,0]]

Output: [0,1]

Explanation: There are 2 courses. To take course 1 you should have finished course 0. So the correct order is [0,1].

Example 2

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]

Output: [0,2,1,3] or [0,1,2,3]

Explanation: There are 4 courses. Course 0 has no prerequisites. Courses 1 and 2 both require course 0. Course 3 requires both 1 and 2. Multiple valid orderings exist.

Example 3

Input: numCourses = 1, prerequisites = []

Output: [0]

Explanation: Only one course with no prerequisites.

Constraints

•1 <= numCourses <= 2000
•0 <= prerequisites.length <= numCourses * (numCourses - 1)
•prerequisites[i].length == 2
•0 <= ai, bi < numCourses
•ai != bi
•All the pairs [ai, bi] are distinct

Show Hints (5)

Hint 1: This is a classic topological sort problem. What algorithm gives you the sorted order?

Hint 2: Kahn's algorithm (BFS) processes nodes with in-degree 0 and builds the result as it goes.

Hint 3: DFS-based topological sort adds nodes to the result in reverse post-order.

Hint 4: If the result array has fewer elements than numCourses, there must be a cycle.

Hint 5: What data structures do you need? Think about storing the graph and tracking in-degrees.

Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor

Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?