Skip to main content
DSA patterns

Course Schedule II

mediumGraphs Must-doGoogleMetaAWSHashiCorp

Problem statement

There are numCourses courses, numbered 0 to numCourses - 1. Each pair [a, b] in prerequisites means you must finish course b before you can start course a.

Return an order in which you can take all the courses. If several orders work, return any of them. If no order works — because some courses depend on each other in a circle — return an empty list.

This is exactly the question a deploy tool answers before a rollout: given which services depend on which, in what order should they start? A circular dependency means there is no safe order.

Examples

Example 1

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

Output: [0,1]

Explanation: Course 1 needs course 0 first, so the only valid order is 0 then 1.

Example 2

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

Output: [0,1,2,3]

Explanation: Course 0 has no prerequisites, courses 1 and 2 each need 0, and course 3 needs both 1 and 2. So 0 comes first and 3 comes last; [0,2,1,3] is just as correct.

Example 3

Input: numCourses = 1, prerequisites = []

Output: [0]

Explanation: There is only one course and nothing to wait for, so it is taken on its own.

Hints

Hint 1: Which courses can you take right now, before taking anything else?

Approach

Optimal: DFS with three states

Intuition

Think about a single course. Before you can write it down, all its prerequisites must already be written down. So, to place course c: first place each of its prerequisites (the same way, recursively), then write c. This is a depth-first search (DFS), and because each course is written only after its prerequisites finish, the list comes out in a valid order.

To catch cycles, give each course one of three states: unvisited, in progress (we are still placing its prerequisites), or done. If the DFS reaches a course that is in progress, we've walked in a circle back to a course that is waiting on us — a cycle — so return []. A done course is already written down and can be skipped.

Steps

  1. Build needs[c]: the prerequisites of each course. Set every state to unvisited.
  2. Define place(c):
    • If c is in progress, return false (cycle).
    • If c is done, return true.
    • Mark c in progress. Call place(p) for each p in needs[c]; if any returns false, return false.
    • Mark c done, add it to order, and return true.
  3. Call place(c) for every course c from 0 up. If any call returns false, return [].
  4. Return order.

Dry run

Example 2: needs = {0: [], 1: [0], 2: [0], 3: [1, 2]}

call what happens order
place(0) no prerequisites → done [0]
place(1) needs 0 (done) → done [0, 1]
place(2) needs 0 (done) → done [0, 1, 2]
place(3) needs 1, 2 (both done) → done [0, 1, 2, 3]

Edge case: with [[1,0],[0,1]], place(0) marks 0 in progress and calls place(1), which marks 1 in progress and calls place(0) — 0 is in progress, so it's a cycle → [].

Complexity

Time O(n + E) - Each course is fully explored only once; after that it is marked done and every later visit returns at once. Exploring a course looks at each of its prerequisites once, so every pair is followed once in total. Together that is linear in courses plus pairs, the same as Kahn's.

Space O(n + E) - The prerequisite lists hold all E pairs. The state list and the output are O(n). The recursion can go n calls deep on a long chain, which is why the Python code raises its recursion limit.

import sys
from typing import List

sys.setrecursionlimit(10000)  # a chain of 2,000 courses recurses 2,000 deep


class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        needs: List[List[int]] = [[] for _ in range(numCourses)]
        for course, pre in prerequisites:
            needs[course].append(pre)

        UNVISITED, IN_PROGRESS, DONE = 0, 1, 2
        state = [UNVISITED] * numCourses
        order: List[int] = []

        def place(c: int) -> bool:
            if state[c] == IN_PROGRESS:
                return False
            if state[c] == DONE:
                return True
            state[c] = IN_PROGRESS
            for p in needs[c]:
                if not place(p):
                    return False
            state[c] = DONE
            order.append(c)
            return True

        for c in range(numCourses):
            if not place(c):
                return []
        return order


if __name__ == "__main__":
    print(str(Solution().findOrder(2, [[1, 0]])).replace(" ", ""))  # [0,1]
    print(str(Solution().findOrder(4, [[1, 0], [2, 0], [3, 1], [3, 2]])).replace(" ", ""))  # [0,1,2,3]
    print(str(Solution().findOrder(1, [])).replace(" ", ""))  # [0]
RecapThe whole problem in a few lines, for the night before
  • Spot it: "in what order can we do tasks with prerequisites?" or "is there a circular dependency?"
  • Idea: Kahn's — count missing prerequisites per task, repeatedly take a task with count 0 and lower the counts it unlocks
  • Cost: O(n + E) time, O(n + E) space
  • Trap: forgetting the cycle check — if fewer than n tasks were taken, return an empty list
  • Remember: DFS alternative needs three states (unvisited, in progress, done) to tell a cycle from a shared prerequisite

Interview follow-ups

  • Return the actual cycle when no order exists.

    Use the DFS approach and keep the current path in a list, pushing a course when it goes in progress and popping it when it's done. When you reach a course that is in progress, the cycle is the part of the path from that course to the end. Time and space stay O(n + E). Printing the cycle is what makes a "circular dependency" error message useful.

  • You can take up to k courses at the same time. What's the fewest number of terms?

    Without the limit k, run Kahn's in layers: each round takes everything currently in the queue, and the number of rounds is the answer. That is the length of the longest dependency chain. With a limit k, the problem gets much harder in general (it is LeetCode's Parallel Courses II), so say that and fall back to taking up to k ready courses per round as a heuristic.

  • New dependencies are added over time. How do you avoid rerunning the whole sort?

    When a new pair b → a arrives and b already comes before a in the current order, nothing changes. Otherwise, only the courses between them in the order need to be reshuffled, and a cycle exists if a can reach b. A simple production approach is to check reachability from a to b first (to reject cycles early) and re-sort only when the order actually breaks.

Frequently asked questions

It is an ordering of the nodes of a directed graph where every edge points forward: if b must come before a, then b appears earlier in the list. It exists only when the graph has no cycle. Course schedules, build steps and service start-up orders are all topological sorts.

Both. Courses 1 and 2 each depend only on 0, so either can go first, and the problem accepts any valid order. The code on this page happens to pick the lower-numbered course first. If you want [0,2,1,3], you'd get it from a different queue order or from the "reverse post-order" style of DFS.

Both are O(n + E). Kahn's is iterative, so it never hits a recursion limit, and "the queue ran dry before all courses were taken" is an easy cycle check to explain. DFS is shorter once you know the three-state trick, and it can report the actual cycle. In an interview, pick the one you can explain clearly.

With only "visited", you can't tell two very different cases apart. Reaching a course that's already done is fine — it's a shared prerequisite, like course 0 in Example 2. Reaching a course that's still in progress means you walked in a circle. The third state is what separates "seen before" from "cycle".

Deciding a safe order from a list of dependencies is everywhere in infra. Terraform orders resource creation this way, package managers order installs, build systems order compile steps, and orchestrators order service start-up. Detecting a circular dependency before a rollout is the same cycle check.