210. Course Schedule II (Medium)

Problem

There are numCourses courses labeled 0 to numCourses - 1. Given prerequisites [a, b] meaning course b must be taken before a, return any ordering of courses you should take to finish all courses. If impossible, return [].

Example

numCourses = 2, prerequisites = [[1, 0]] → [0, 1]
numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] → [0, 1, 2, 3] or [0, 2, 1, 3]
Cyclic prerequisites → []

LeetCode 210 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, check feasibility first, then try to order

Swift

final class Solution {
    func findOrder(_ numCourses: Int, _ prerequisites: [[Int]]) -> [Int] {
        var requires = Array(repeating: [Int](), count: numCourses)
        for edge in prerequisites { requires[edge[0]].append(edge[1]) }
        var state = Array(repeating: 0, count: numCourses)
        func feasible(_ course: Int) -> Bool {
            if state[course] == 1 { return false }
            if state[course] == 2 { return true }
            state[course] = 1
            for prerequisite in requires[course] where !feasible(prerequisite) { return false }
            state[course] = 2
            return true
        }
        guard (0..<numCourses).allSatisfy(feasible) else { return [] }
        var indegree = Array(repeating: 0, count: numCourses)
        var graph = Array(repeating: [Int](), count: numCourses)
        for edge in prerequisites { graph[edge[1]].append(edge[0]); indegree[edge[0]] += 1 }
        var queue = (0..<numCourses).filter { indegree[$0] == 0 }, head = 0, order: [Int] = []
        while head < queue.count {
            let course = queue[head]; head += 1; order.append(course)
            for next in graph[course].sorted() { indegree[next] -= 1; if indegree[next] == 0 { queue.append(next) } }
        }
        return order
    }
}

Use problem 207 to check for cycles. If none, use a second pass to build the order. Two passes, wasted work.

Complexity

Time: $O(V + E)$ × 2 = $O(V + E)$ .
Space: $O(V + E)$ .

Approach 2: DFS post-order (reversed)

Topological order = reversed post-order of a DFS traversal (on a DAG).

from collections import defaultdict

def find_order(num_courses, prerequisites):
    graph = defaultdict(list)                  # L1: O(E) to build
    for a, b in prerequisites:                 # L2: iterate edges
        graph[b].append(a)                     # L3: O(1) per edge

    WHITE, GRAY, BLACK = 0, 1, 2               # L4: constants
    color = [WHITE] * num_courses              # L5: O(V) array
    order = []                                 # L6: result list
    has_cycle = False                          # L7: flag

    def dfs(n):                                # L8: inner DFS
        nonlocal has_cycle
        if has_cycle:                          # L9: early exit
            return
        color[n] = GRAY                        # L10: mark in-progress
        for nb in graph[n]:                    # L11: visit neighbors, O(deg) total per node
            if color[nb] == WHITE:
                dfs(nb)                        # L12: recurse on unvisited
            elif color[nb] == GRAY:
                has_cycle = True               # L13: back edge = cycle
                return
        color[n] = BLACK                       # L14: mark done
        order.append(n)                        # L15: O(1) amortized

    for c in range(num_courses):               # L16: visit every node
        if color[c] == WHITE:
            dfs(c)                             # L17: O(V + E) total across all calls

    if has_cycle:
        return []
    return order[::-1]                         # L18: O(V) reverse

function findOrder(numCourses: number, prerequisites: number[][]): number[] {
    const graph: number[][] = Array.from({ length: numCourses }, () => []);
    for (const [a, b] of prerequisites) graph[b].push(a);  // L1-L3: build graph

    const WHITE = 0, GRAY = 1, BLACK = 2;
    const color = new Array(numCourses).fill(WHITE);        // L5: O(V) array
    const order: number[] = [];                             // L6: result list
    let hasCycle = false;                                   // L7: flag

    function dfs(n: number): void {                         // L8: inner DFS
        if (hasCycle) return;                               // L9: early exit
        color[n] = GRAY;                                    // L10: mark in-progress
        for (const nb of graph[n]) {                        // L11: visit neighbors
            if (color[nb] === WHITE) dfs(nb);               // L12: recurse on unvisited
            else if (color[nb] === GRAY) { hasCycle = true; return; }  // L13: cycle
        }
        color[n] = BLACK;                                   // L14: mark done
        order.push(n);                                      // L15: O(1) amortized
    }

    for (let c = 0; c < numCourses; c++) {                  // L16: visit every node
        if (color[c] === WHITE) dfs(c);                     // L17: O(V + E) total
    }

    if (hasCycle) return [];
    return order.reverse();                                  // L18: O(V) reverse
}

func findOrder(numCourses int, prerequisites [][]int) []int {
    graph := make([][]int, numCourses)
    for _, p := range prerequisites { graph[p[1]] = append(graph[p[1]], p[0]) } // L1-L3

    const white, gray, black = 0, 1, 2
    color := make([]int, numCourses)              // L5: O(V) array
    order := []int{}                              // L6: result
    hasCycle := false                             // L7: flag

    var dfs func(n int)
    dfs = func(n int) {
        if hasCycle { return }                    // L9: early exit
        color[n] = gray                           // L10: mark in-progress
        for _, nb := range graph[n] {             // L11: visit neighbors
            if color[nb] == white { dfs(nb) }     // L12: recurse on unvisited
            if color[nb] == gray { hasCycle = true; return } // L13: cycle
        }
        color[n] = black                          // L14: mark done
        order = append(order, n)                  // L15
    }

    for c := 0; c < numCourses; c++ {             // L16
        if color[c] == white { dfs(c) }           // L17
    }
    if hasCycle { return []int{} }
    for i, j := 0, len(order)-1; i < j; i, j = i+1, j-1 { order[i], order[j] = order[j], order[i] } // L18
    return order
}

final class Solution {
    func findOrder(_ numCourses: Int, _ prerequisites: [[Int]]) -> [Int] {
        var graph = Array(repeating: [Int](), count: numCourses)
        for edge in prerequisites { graph[edge[0]].append(edge[1]) }
        var state = Array(repeating: 0, count: numCourses), order: [Int] = []
        func visit(_ course: Int) -> Bool {
            if state[course] == 1 { return false }
            if state[course] == 2 { return true }
            state[course] = 1
            for prerequisite in graph[course].sorted() where !visit(prerequisite) { return false }
            state[course] = 2; order.append(course)
            return true
        }
        for course in 0..<numCourses where !visit(course) { return [] }
        return order
    }
}

Where the time goes, line by line

Variables: V = numCourses, E = len(prerequisites).

Line	Per-call cost	Times executed	Contribution
L1-L3 (build graph)	$O(1)$ per edge	E	$O(E)$
L5 (color array)	$O(V)$	1	$O(V)$
L16-L17 (outer loop + DFS)	$O(1)$ per node/edge	V + E total	$O(V + E)$
L11-L12 (neighbor traversal inside DFS)	$O(1)$ per edge	E total	$O(V + E)$ ← dominates
L18 (reverse)	$O(V)$	1	$O(V)$

Each node is colored WHITE → GRAY → BLACK exactly once, and each edge is examined exactly once during the neighbor loops. The total DFS cost across all calls in L16-L17 is $O(V + E)$ , not $O(V × E)$ .

Complexity

Time: $O(V + E)$ , driven by L11-L12 (each node and edge visited once).
Space: $O(V + E)$ for the graph and recursion stack.

Approach 3: Kahn’s algorithm (BFS on in-degree), optimal and natural

Incrementally process zero-in-degree nodes; the output order is the topological sort.

from collections import defaultdict, deque

def find_order(num_courses, prerequisites):
    graph = defaultdict(list)                  # L1: adjacency list
    in_deg = [0] * num_courses                 # L2: O(V) in-degree array
    for a, b in prerequisites:                 # L3: O(E) to populate
        graph[b].append(a)                     # L4: O(1) per edge
        in_deg[a] += 1                         # L5: O(1) per edge

    q = deque([i for i in range(num_courses)   # L6: O(V) seed queue
               if in_deg[i] == 0])
    order = []                                 # L7: result
    while q:                                   # L8: outer BFS loop
        n = q.popleft()                        # L9: O(1)
        order.append(n)                        # L10: O(1) amortized
        for nb in graph[n]:                    # L11: visit neighbors
            in_deg[nb] -= 1                    # L12: O(1)
            if in_deg[nb] == 0:
                q.append(nb)                   # L13: O(1) amortized

    return order if len(order) == num_courses else []  # L14: O(1)

function findOrder(numCourses: number, prerequisites: number[][]): number[] {
    const graph: number[][] = Array.from({ length: numCourses }, () => []);
    const inDeg = new Array(numCourses).fill(0);  // L2: O(V) in-degree array
    for (const [a, b] of prerequisites) {          // L3: O(E) to populate
        graph[b].push(a);                          // L4: O(1) per edge
        inDeg[a]++;                                // L5: O(1) per edge
    }

    const q: number[] = [];
    for (let i = 0; i < numCourses; i++) {         // L6: O(V) seed queue
        if (inDeg[i] === 0) q.push(i);
    }
    const order: number[] = [];                    // L7: result
    let head = 0;
    while (head < q.length) {                      // L8: outer BFS loop
        const n = q[head++];                       // L9: O(1)
        order.push(n);                             // L10: O(1) amortized
        for (const nb of graph[n]) {               // L11: visit neighbors
            inDeg[nb]--;                           // L12: O(1)
            if (inDeg[nb] === 0) q.push(nb);       // L13: O(1) amortized
        }
    }

    return order.length === numCourses ? order : [];  // L14: O(1)
}

func findOrder(numCourses int, prerequisites [][]int) []int {
    graph := make([][]int, numCourses)
    inDeg := make([]int, numCourses)              // L2: O(V) in-degree array
    for _, p := range prerequisites {             // L3: O(E) to populate
        graph[p[1]] = append(graph[p[1]], p[0])  // L4
        inDeg[p[0]]++                             // L5
    }
    queue := []int{}
    for i := 0; i < numCourses; i++ {             // L6: seed queue
        if inDeg[i] == 0 { queue = append(queue, i) }
    }
    order := []int{}                              // L7
    for len(queue) > 0 {                          // L8
        n := queue[0]; queue = queue[1:]          // L9
        order = append(order, n)                  // L10
        for _, nb := range graph[n] {             // L11
            inDeg[nb]--                           // L12
            if inDeg[nb] == 0 { queue = append(queue, nb) } // L13
        }
    }
    if len(order) == numCourses { return order }  // L14
    return []int{}
}

final class Solution {
    func findOrder(_ numCourses: Int, _ prerequisites: [[Int]]) -> [Int] {
        var graph = Array(repeating: [Int](), count: numCourses)
        var indegree = Array(repeating: 0, count: numCourses)
        for edge in prerequisites { graph[edge[1]].append(edge[0]); indegree[edge[0]] += 1 }
        var queue = (0..<numCourses).filter { indegree[$0] == 0 }, head = 0, order: [Int] = []
        while head < queue.count {
            let course = queue[head]; head += 1; order.append(course)
            for next in graph[course].sorted() { indegree[next] -= 1; if indegree[next] == 0 { queue.append(next) } }
        }
        return order.count == numCourses ? order : []
    }
}

Where the time goes, line by line

Variables: V = numCourses, E = len(prerequisites).

Line	Per-call cost	Times executed	Contribution
L1-L5 (build graph + in-degree)	$O(1)$ per edge	E	$O(E)$
L6 (seed queue)	$O(V)$	1	$O(V)$
L8-L10 (dequeue each node)	$O(1)$	V	$O(V)$
L11-L13 (neighbor loop)	$O(1)$ per edge	E total	$O(V + E)$ ← dominates
L14 (length check)	$O(1)$	1	$O(1)$

Each node enters the queue at most once (when its in-degree hits zero), and each edge is decremented exactly once in L12. The BFS processes the entire graph in a single $O(V + E)$ pass, with no recursion overhead.

Complexity

Time: $O(V + E)$ , driven by L11-L13 (every edge decremented once).
Space: $O(V + E)$ for the graph, in-degree array, and queue.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space	Notes
Two-pass (cycle + order)	$O(V + E)$	$O(V + E)$	Redundant
DFS post-order reversed	$O(V + E)$	$O(V + E)$	Elegant
Kahn’s (BFS in-degree)	$O(V + E)$	$O(V + E)$	Most natural for this problem

Kahn’s is usually the cleanest answer here, you get feasibility and ordering in one pass. DFS post-order is worth knowing because it generalizes to problems where you need a specific topological ordering (e.g., tie-breaking alphabetically).

# Quick smoke tests, paste into a REPL or save as test_210.py and run.
# Uses Kahn's algorithm (Approach 3) as the canonical implementation.

from collections import defaultdict, deque

def find_order(num_courses, prerequisites):
    graph = defaultdict(list)
    in_deg = [0] * num_courses
    for a, b in prerequisites:
        graph[b].append(a)
        in_deg[a] += 1
    q = deque([i for i in range(num_courses) if in_deg[i] == 0])
    order = []
    while q:
        n = q.popleft()
        order.append(n)
        for nb in graph[n]:
            in_deg[nb] -= 1
            if in_deg[nb] == 0:
                q.append(nb)
    return order if len(order) == num_courses else []

def _run_tests():
    # Example 1: simple two-course chain
    assert find_order(2, [[1, 0]]) == [0, 1]

    # Example 2: four courses, multiple valid orderings
    result = find_order(4, [[1,0],[2,0],[3,1],[3,2]])
    assert result.index(0) < result.index(1)
    assert result.index(0) < result.index(2)
    assert result.index(1) < result.index(3)
    assert result.index(2) < result.index(3)

    # Cycle: impossible
    assert find_order(2, [[1, 0],[0, 1]]) == []

    # Single course, no prerequisites
    assert find_order(1, []) == [0]

    # No prerequisites at all
    result = find_order(3, [])
    assert set(result) == {0, 1, 2}

    # Longer cycle
    assert find_order(3, [[0,1],[1,2],[2,0]]) == []

    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function findOrder(numCourses: number, prerequisites: number[][]): number[] {
    const graph: number[][] = Array.from({ length: numCourses }, () => []);
    const inDeg = new Array(numCourses).fill(0);
    for (const [a, b] of prerequisites) { graph[b].push(a); inDeg[a]++; }
    const q: number[] = [];
    for (let i = 0; i < numCourses; i++) if (inDeg[i] === 0) q.push(i);
    const order: number[] = [];
    let head = 0;
    while (head < q.length) {
        const n = q[head++];
        order.push(n);
        for (const nb of graph[n]) { inDeg[nb]--; if (inDeg[nb] === 0) q.push(nb); }
    }
    return order.length === numCourses ? order : [];
}

console.assert(JSON.stringify(findOrder(2, [[1, 0]])) === JSON.stringify([0, 1]));
const r = findOrder(4, [[1,0],[2,0],[3,1],[3,2]]);
console.assert(r.indexOf(0) < r.indexOf(1) && r.indexOf(0) < r.indexOf(2));
console.assert(JSON.stringify(findOrder(2, [[1,0],[0,1]])) === JSON.stringify([]));
console.assert(JSON.stringify(findOrder(1, [])) === JSON.stringify([0]));
console.assert(JSON.stringify(findOrder(3, [[0,1],[1,2],[2,0]])) === JSON.stringify([]));
console.log("all tests pass");

Graphs, topological sort (Kahn’s vs. DFS post-order)

Topological Sort, the dependency order pattern for prerequisites and directed acyclic graphs.
Graph Traversal, the visited set model for exploring nodes and edges without repetition.

210. Course Schedule II (Medium)

Problem

Try it yourself

Approach 1: Brute force, check feasibility first, then try to order

Approach 2: DFS post-order (reversed)

Approach 3: Kahn’s algorithm (BFS on in-degree), optimal and natural

Summary

Test cases

Related data structures

Related concepts