Course Schedule

Prerequisites, build steps, package dependencies, spreadsheet formulas: whenever one thing must happen before another, you have a directed graph, and the question is whether an order exists that respects every "before". That order is a topological order, and finding one is one of the most asked graph problems.

The problem

There are n courses numbered 0 to n − 1, and a list of pairs [course, needs], meaning needs must be taken before course. Return an order in which all courses can be taken. If there is no such order, return an empty list. (The yes/no version — "can all courses be finished?" — is the same problem.)

Example 1. Five courses: 0 is Introduction to Programming. Discrete Mathematics (1) and Data Structures (2) both need 0. Algorithms (3) needs 1 and 2. Databases (4) needs 2. n = 5, pairs [[1, 0], [2, 0], [3, 1], [3, 2], [4, 2]] → [0, 1, 2, 3, 4]. Other orders, such as [0, 2, 4, 1, 3], are also correct.

Example 2. n = 4, pairs [[1, 0], [2, 1], [0, 2]] → []. Courses 0, 1 and 2 each wait for another in a circle, so none can ever start.

Constraints. Up to 10^5 courses and 10^5 pairs.

Clarifying questions

• Which way does a pair point? [course, needs]: the edge goes from needs to course. Getting this backwards produces a reversed order — ask.
• Can a pair repeat? Assume it may; the solution counts it twice on both sides, which is harmless.
• Any valid order, or a specific one? Any valid order.
• Can a course need itself? That is a cycle of length one: return [].

Approach 1: the simple way

Do what a student would do. Sweep through the courses; take any course whose prerequisites are all taken. Keep sweeping until a full sweep takes nothing.

1def find_order_brute(n: int, prerequisites: list[list[int]]) -> list[int]:2    """Keep sweeping all courses, taking any whose prerequisites are all done."""3    needs: list[list[int]] = [[] for _ in range(n)]4    for course, pre in prerequisites:5        needs[course].append(pre)6    taken = [False] * n7    order: list[int] = []8    progress = True9    while progress:10        progress = False11        for course in range(n):12            if not taken[course] and all(taken[p] for p in needs[course]):13                taken[course] = True14                order.append(course)15                progress = True16    return order if len(order) == n else []

Each sweep costs O(n + E). How many sweeps? If the courses form a chain listed backwards — course 0 needs 1, 1 needs 2, and so on — each sweep takes only one course, so there are n sweeps: O(n × (n + E)). With 10^5 courses that is about 10^10 checks. The waste: every sweep re-checks courses whose prerequisites have not changed at all.

The key insight

A course becomes available at one precise moment: when its last prerequisite is taken. So do not re-check it; count down. Give each course an in-degree — the number of prerequisites it still waits for. When you take a course, subtract 1 from each course it unlocks. The ones that reach 0 are now available; put them in a queue.

This is Kahn's algorithm. It also detects cycles for free. Every course in a cycle waits for another course in the same cycle, so none of their counts ever reaches 0. They are never taken, and the order comes out shorter than n.

Approach 2: Kahn's algorithm

1from collections import deque234def find_order(n: int, prerequisites: list[list[int]]) -> list[int]:5    """Kahn's algorithm. Returns a valid order, or [] if a cycle blocks it."""6    unlocks: list[list[int]] = [[] for _ in range(n)]7    in_degree = [0] * n8    for course, pre in prerequisites:9        unlocks[pre].append(course)              # edge: pre -> course10        in_degree[course] += 111    queue = deque(c for c in range(n) if in_degree[c] == 0)12    order: list[int] = []13    while queue:14        course = queue.popleft()15        order.append(course)16        for nxt in unlocks[course]:17            in_degree[nxt] -= 1                  # one prerequisite done18            if in_degree[nxt] == 0:19                queue.append(nxt)20    return order if len(order) == n else []212223def can_finish(n: int, prerequisites: list[list[int]]) -> bool:24    """Course Schedule I is the same computation, asked as yes or no."""25    return len(find_order(n, prerequisites)) == n

Step by step:

1. Build unlocks (edges from prerequisite to course) and count each course's in-degree.
2. Queue every course with in-degree 0 — nothing blocks it.
3. Pop a course, append it to the order, and decrement each course it unlocks. Any that reach 0 join the queue.
4. If all n courses came out, the order is valid. If fewer did, the rest are stuck in or behind a cycle.

Dry run on Example 1. Starting in-degrees: course 0 → 0, 1 → 1, 2 → 1, 3 → 2, 4 → 1.

Five courses out of five: valid. Check one edge: Databases (4) needs Data Structures (2), and 2 comes before 4.

On Example 2, the in-degrees of 0, 1 and 2 are all 1, and course 3 has 0. The queue starts as [3], takes it, and stops. The order [3] has length 1, not 4, so the answer is [].

Complexity. Time O(V + E): each course is queued once, and each pair is used once to build the graph and once to decrement. Space O(V + E) for the lists. On 10^5 courses and pairs, that is a few hundred thousand steps instead of 10^10.

Approach 3: DFS with three colours

A topological order can also come from DFS. When a course finishes — all the courses it unlocks are fully explored — push it onto a list. Reversed, that list is a valid order. Cycle detection needs three states: white (not seen), grey (on the current DFS path) and black (done). Meeting a grey course means you have walked in a circle.

1def find_order_dfs(n: int, prerequisites: list[list[int]]) -> list[int]:2    """DFS with three colours; reversed finish order is a topological order."""3    unlocks: list[list[int]] = [[] for _ in range(n)]4    for course, pre in prerequisites:5        unlocks[pre].append(course)6    WHITE, GREY, BLACK = 0, 1, 2                 # unseen, on the current path, done7    colour = [WHITE] * n8    finished: list[int] = []910    def visit(u: int) -> bool:11        colour[u] = GREY12        for v in unlocks[u]:13            if colour[v] == GREY:14                return False                     # back edge: a cycle15            if colour[v] == WHITE and not visit(v):16                return False17        colour[u] = BLACK18        finished.append(u)19        return True2021    for u in range(n):22        if colour[u] == WHITE and not visit(u):23            return []24    return finished[::-1]

On Example 1 it returns [0, 2, 4, 1, 3] — different from Kahn's, and equally valid. It is also O(V + E), but it recurses up to V deep, and the grey/black distinction is easy to get wrong under pressure. Lead with Kahn's; mention this one.

Edge cases

• No pairs → every course has in-degree 0; any order of 0 to n − 1 is valid.
• A course that needs itself → its in-degree never reaches 0: [].
• A cycle plus independent courses → the independent ones come out, but the count is short: [].
• Duplicate pairs → the in-degree counts the pair twice and so do the decrements; it still reaches 0 at the right time.

Follow-ups

• "Just say whether it is possible." Return len(order) == n — the same function, as can_finish shows.
• "Minimum number of semesters, taking any number of courses at once." Run Kahn's level by level, like the minutes in Rotting Oranges: each level of the queue is one semester.
• "Recover the letter order of an alien alphabet from a sorted word list." Compare each pair of neighbouring words; the first differing letters give one edge. Then topological sort the letters.