Skip to main content

210. Course Schedule II

medium

Return a valid order to finish all courses given their prerequisites, or an empty array if impossible. Course Schedule I asks 'can it be done?' — this asks 'show me the schedule.' Kahn's topological sort produces the order as a free byproduct.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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 many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

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.

Examples

Example 1

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

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

Example 2

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

Explanation: There are 4 courses. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another is [0,2,1,3].

Example 3

Input
numCourses = 1, prerequisites = []
Output
[0]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Exact same setup as Course Schedule I — but instead of just counting, record the order in which you pop nodes.

Hint 2

Kahn's BFS naturally produces a topological order: every node is pushed exactly once, in dependency-respecting sequence.

Hint 3

If the recorded order has fewer than numCourses entries at the end, a cycle existed — return [].

Solution approach

Reveal approach

Build adjacency list and in-degree array from prerequisites (b -> a means b must come before a). Seed a queue with every 0-in-degree node. Pop nodes one at a time and append to a result list, decrementing each neighbor's in-degree and enqueueing those that hit 0. After the queue drains, if result.length == numCourses return result, else return [] (a cycle prevented some nodes from reaching in-degree 0). The append-as-you-pop is the entire trick — Kahn's naturally produces a valid topological order. O(V + E) time, O(V + E) space.

Complexity

Time
O(V + E)
Space
O(V + E)

Related patterns

  • topological-sort
  • bfs
  • dfs
  • graph

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Microsoft
  • Meta
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Course Schedule II and Graphs problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →