LeetCode 210 · Graphs

Course Schedule II, explained with a picture

A timetable that respects every prerequisite.

MediumGraphs
▶ Watch it step by step

The problem

Same setup as Course Schedule, but return one valid order in which to take all courses, or an empty list if it’s impossible.

Input:  n = 6, prerequisites 1-0, 2-0, 3-1, 3-2, 4-3, 5-2
Output: [0, 1, 2, 3, 5, 4]

Picture it

Same course map. Every time a course becomes free (no unfinished prerequisites), we add it to the timetable. The order in which courses are taken is the answer. If the timetable ends up shorter than n, some courses were in a loop.

How to recognise it

  • Like Course Schedule, but you must produce an order, not only say whether one exists.
  • "Must come before" rules form a directed graph, and any order that respects every rule is accepted.
  • An empty answer signals a cycle, so the algorithm must notice cycles as well as build the order.
  • With up to 2,000 courses, trying orderings (2,000! of them) is out of the question, and even 12 courses already have 479 million.

Start with brute force

Build the order one course at a time: scan all courses, take the first one that has not been taken and whose prerequisites are all taken, and repeat. If a full scan finds nothing, there is a cycle.

def find_order_brute(n, prerequisites):
    needs = defaultdict(list)
    for course, need in prerequisites:
        needs[course].append(need)
    taken, done = [], set()
    while len(taken) < n:
        for c in range(n):
            if c not in done and all(b in done for b in needs[c]):
                taken.append(c)
                done.add(c)
                break
        else:
            return []
    return taken

Each of the n rounds scans up to V courses and all their prerequisites, so time is O(V·(V + E)): about 1.4 × 10^7 steps for 2,000 courses and 5,000 rules, but about 10^10 for 10^5 of each. Space is O(V + E).

From brute force to the idea

  1. Find the waste. Every round rechecks courses whose situation has not changed. Only courses that depend on the course just taken can become free.
  2. Track unmet prerequisites. indeg[c] counts them, and nxt[need] lists the courses that wait for need.
  3. Queue the free ones. Every course with indeg == 0 goes into the queue. Taking one means appending it to taken.
  4. Update only the neighbours. When course c is taken, decrease indeg for each course in nxt[c]. Any that drops to 0 is now free and is queued.
  5. The order is the answer. taken already respects all rules, because a course is added only after all its prerequisites were. If len(taken) < n, some courses sit on a cycle and the function returns [].

The key idea: the order in which Kahn's algorithm takes courses is itself a valid schedule.

The key idea

Topological order from Kahn’s algorithm; length < n means a cycle.

Python solution

def find_order(n, prerequisites):
    indeg = [0] * n; nxt = defaultdict(list)
    for course, need in prerequisites:
        nxt[need].append(course); indeg[course] += 1
    q = deque(c for c in range(n) if indeg[c] == 0)
    taken = []
    while q:
        c = q.popleft()
        taken.append(c)
        for d in nxt[c]:
            indeg[d] -= 1
            if indeg[d] == 0:
                q.append(d)
    return taken if len(taken) == n else []

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import defaultdict, deque

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(V·(V + E)): n rounds, each scanning courses and their prerequisitesO(V + E): the lists and the done set
Kahn's algorithm (shown code)O(V + E): each course is queued once and each rule is processed onceO(V + E): the adjacency lists, in-degrees, queue and result

Edge cases

  • No rules (n = 3, []): returns [0, 1, 2].
  • One chain (n = 2, [[1, 0]]): returns [0, 1], because course 0 must come first. The pair [a, b] means "a needs b".
  • A cycle ([[0,1],[1,0]]): returns [].
  • A cycle plus free courses: the free ones are taken, but the length check still fails, so the result is [], not a partial order.
  • Several valid orders: any is accepted. For [[1,0],[2,0],[3,1],[3,2]] the shown code gives [0, 1, 2, 3].
  • n = 0: returns [], the same as the "impossible" answer. deque and defaultdict must be imported.

Common mistakes

  • Returning the partial list when a cycle exists, instead of [].
  • Reversing the pair, which produces an order where each course comes before its prerequisite.
  • Returning taken[::-1], which is valid only for the opposite arrow convention.
  • Keeping only courses that appear in a rule, so independent courses are missing.
  • Marking a course taken when its first prerequisite is done instead of its last.
Your turn: the smallest valid order

Of all valid orders, return the one that is smallest when compared as lists (so course 0 comes as early as possible, then course 1, and so on). Return [] if impossible. Describe what changes, then write it if you like.

Compare with our answer

Kahn's algorithm stays the same, but the free courses go into a min-heap instead of a plain queue, so the smallest free course is always taken next.

import heapq

def smallest_order(n, prerequisites):
    indeg = [0] * n
    nxt = defaultdict(list)
    for course, need in prerequisites:
        nxt[need].append(course)
        indeg[course] += 1
    heap = [c for c in range(n) if indeg[c] == 0]
    heapq.heapify(heap)
    taken = []
    while heap:
        c = heapq.heappop(heap)
        taken.append(c)
        for d in nxt[c]:
            indeg[d] -= 1
            if indeg[d] == 0:
                heapq.heappush(heap, d)
    return taken if len(taken) == n else []

smallest_order(4, [[0, 3], [1, 2]]) is [2, 1, 3, 0], because 3 and 2 must come before 0 and 1. Time O((V + E) log V), space O(V + E).

A strong answer mentions: replacing the queue with a heap, that each free course is chosen greedily as the smallest, and the extra log factor.

Check what stuck

1. Database migrations come with rules "migration A must run before B". You must print one order that runs them all, or fail if the rules contradict each other. Which approach fits best?

2. Why does the shown solution run in O(V + E) time?

3. A learner changes the last line to return taken[::-1] when a valid order exists. Which input still returns a valid order?

Score 60% or more and the lesson is marked complete.