Course Schedule II

Problem

There are a total of numCourses courses you have to take. 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 it is impossible to finish all courses, return an empty array.

Examples

The brute-force approach

Try all permutations of courses. For each permutation, check that every prerequisite is satisfied (prerequisite appears earlier). Return the first valid permutation.

for perm in all_permutations(range(numCourses)):
    valid = True
    for [a, b] in prerequisites:
        if perm.index(b) >= perm.index(a):
            valid = False
    if valid: return perm
return []

O(numCourses!) permutations, each taking O(numCourses + prerequisites) to verify. Completely impractical.

Spotting the pattern

This is a Topological Sort problem. The key question to ask yourself:

In Course Schedule I you counted how many nodes you processed. What small addition to the same algorithm gives you the ordering itself?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.