Course Schedule II

Explanation & Solution

Description

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.

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

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

Output:[0,1]

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

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

Approach

Topological Sort pattern

1. Build the Graph and In-Degree Array

Create a directed adjacency list: edge from prereq → course
For each prerequisite pair [course, prereq], add course to graph[prereq]
Increment inDegree[course] to count how many prerequisites it has

2. Initialize the Queue

Scan all courses and enqueue those with inDegree === 0
These are the courses with no prerequisites that can be taken first

3. BFS Topological Sort (Kahn's Algorithm)

Dequeue a course and append it to the order result array
For each dependent course, decrement its in-degree
When a course's in-degree reaches 0, all its prerequisites have been processed — enqueue it

4. Detect Cycles and Return Result

If order.length === numCourses, a valid ordering was found — return it
If order.length < numCourses, a cycle exists and some courses can never be taken — return []

Key Insight

This extends Course Schedule I by recording the topological order instead of just checking its existence
Kahn's algorithm naturally produces one valid topological ordering via BFS
Multiple valid orderings may exist when several courses have the same in-degree at a given step

Time

O(V + E) where V = numCourses and E = number of prerequisites

Space

O(V + E) for the graph, in-degree array, and result

Solution Code

Course Schedule

Alien Dictionary