Skip to content

Volume ITechnology

4.20.9 — Course Schedule II ​

LeetCode 210 · Medium

The problem ​

Return an order in which all courses can be taken, or an empty array if it is impossible.

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

→ [0,1,2,3]   or   [0,2,1,3]     — both valid

In plain English, you must take numCourses courses. You are given an array of prerequisites where prerequisites[i] = [a, b] indicates you must take course b before course a. Return an array of the courses in a valid order to take them. If there are multiple valid orders, return any of them. If it's impossible to take all courses (because of a cycle), return an empty array.

Any valid order is accepted, which matters: a graph usually has many topological orders.

The pattern ​

4.20.8 already computed this. Kahn's algorithm takes courses one at a time in an order that respects every prerequisite — that sequence is the answer. The previous problem simply threw it away and kept the count.

So the change is two lines: collect the courses as you take them, and return the list instead of a boolean.

A picture to hold in mind ​

Think of Kahn's algorithm like writing down a recipe. In Course Schedule I, you were just checking if the recipe could be completed without an impossible loop. In Course Schedule II, you actually write down the steps on a piece of paper as you do them. When you find a step that has no prerequisites (like "get bowl"), you write it down on your order list and mentally cross it off. You keep writing down steps as they become available. The final list you wrote down is your answer!

This is what a topological sort is: an ordering of a directed acyclic graph where every edge points forwards.

The solution ​

python
from collections import deque

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        adj = [[] for _ in range(numCourses)]  # (1)
        indegree = [0] * numCourses

        for course, prereq in prerequisites:  # (2)
            adj[prereq].append(course)           # prereq → course
            indegree[course] += 1

        queue = deque(c for c in range(numCourses) if indegree[c] == 0)  # (3)
        order = []  # (4)

        while queue:
            c = queue.popleft()  # (5)
            order.append(c)                      # (6) ← the only real change
            for nxt in adj[c]:  # (7)
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    queue.append(nxt)

        return order if len(order) == numCourses else []  # (8)
ts
function findOrder(numCourses: number, prerequisites: number[][]): number[] {
  const adj: number[][] = Array.from({ length: numCourses }, () => []);  // (1)
  const indegree = new Array(numCourses).fill(0);

  for (const [course, prereq] of prerequisites) {  // (2)
    adj[prereq].push(course);
    indegree[course]++;
  }

  const queue: number[] = [];  // (3)
  for (let c = 0; c < numCourses; c++) if (indegree[c] === 0) queue.push(c);

  const order: number[] = [];  // (4)
  let head = 0;
  while (head < queue.length) {
    const c = queue[head++];  // (5)
    order.push(c);  // (6)
    for (const nxt of adj[c]) {  // (7)
      if (--indegree[nxt] === 0) queue.push(nxt);
    }
  }

  return order.length === numCourses ? order : [];  // (8)
}

return order if complete else []. A short order means a cycle, and the problem wants an empty array in that case — not the partial order. Returning the partial list is a real bug, because it looks like a valid schedule.

A course enters the queue exactly once, at the moment its last prerequisite is removed. So order holds each course once and its length is the natural completeness check.

Line by line ​

This is 4.20.8 Course Schedule with one change: instead of only counting finished courses, we record them in the order they finish.

(1) Build the graph: for each course, the courses that depend on it, plus

(2) a count of unfinished prerequisites for each course.

(3) Start with every course that has no prerequisites.

(4) The order we will return.

(5) Take a course that is ready. All of its prerequisites have already been taken.

(6) Add it to the order. This is the only real change from Course Schedule. Because a course only becomes ready after all its prerequisites are in the order, every course appears after the courses it needs.

(7) Each dependent course now has one fewer prerequisite. Any that reach zero join the queue.

(8) If every course made it into the order, return it. Otherwise a loop of prerequisites blocked some courses, and no valid order exists, so return an empty list.

The DFS version, and why the order comes out reversed ​

DFS also produces a topological order, with one twist worth understanding.

Do a depth-first walk. When a node has finished — that is, all of its dependents are done — push it onto a list. Then reverse the list at the end.

python
def findOrder(self, numCourses, prerequisites):
    adj = [[] for _ in range(numCourses)]
    for course, prereq in prerequisites:
        adj[prereq].append(course)

    state = [0] * numCourses            # 0 unvisited, 1 in progress, 2 done
    order = []

    def dfs(c) -> bool:
        if state[c] == 1: return False  # cycle
        if state[c] == 2: return True

        state[c] = 1
        for nxt in adj[c]:
            if not dfs(nxt): return False
        state[c] = 2
        order.append(c)                 # finished: everything after it is placed
        return True

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

    return order[::-1]                  # reverse

Why reverse? A node is appended only after every node that depends on it has been appended. So the list is built from the last course backwards, and reversing puts the prerequisites first.

That is the post-order position doing the work, exactly as in the tree chapter: the node acts only after its children are finished.

Edge cases ​

  • No prerequisites. Every course is ready at once, so any order works, and the code returns 0, 1, 2, ….
  • A loop of prerequisites. Some courses never become ready, order is too short, and the answer is [].
  • Several valid orders. The problem accepts any of them. The queue happens to produce one.

Complexity ​

O(V + E) time and space for both versions.

The follow-up: how many semesters ​

If you may take any number of courses at once, provided their prerequisites are done, the minimum number of semesters is the number of levels in Kahn's algorithm.

Everything sitting in the queue at the same moment has no unmet prerequisites and none depends on another, so they can all be taken together. Process the queue level by level, freezing its length as in 4.14.8, and count the rounds.

That number is the longest chain of prerequisites in the graph — the critical path. Real project schedulers compute exactly this, and it is where the term "critical path" comes from.

Where this goes next ​

  • Alien Dictionary — build the graph from sorted words, then topologically sort it. The hard part is deriving the edges, not the sort. 4.21.
  • Parallel Courses, Minimum Time to Complete All Tasks — the level-counting follow-up above.
  • Sequence Reconstruction — is the topological order unique? It is, exactly when the queue never holds more than one node at a time. Neat, and easy to check.
  • Real systems — make, Bazel, npm's dependency resolution, spreadsheet recalculation, and database migration ordering all run this.

What the interviewer will push on ​

"Is the order unique?" No, in general. It is unique exactly when Kahn's queue never holds more than one node.

"What do you return on a cycle?" An empty array. Not the partial order.

"BFS or DFS?" Kahn's is iterative, gives the cycle check for free, and extends to the semester question. DFS needs a reversal and can hit stack limits.

"Why does the DFS order need reversing?" Nodes are appended after everything depending on them, so the list is built backwards.

"How many semesters minimum?" The number of levels, which is the longest prerequisite chain.

One thing to volunteer: point out that this is Course Schedule with two lines changed, and that Kahn's was already computing the order. Recognising that a previous problem's discarded work is this problem's answer is exactly the kind of connection worth showing.

Next: 4.20.10 Redundant Connection — the first union-find problem, where edges arrive one at a time.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet