207. Course Schedule (Medium)

Problem

You are given numCourses courses labeled 0 to numCourses - 1 and an array prerequisites where prerequisites[i] = [a, b] means you must take course b before course a. Return true if you can finish all courses, i.e., the prerequisite graph has no cycles.

Example

numCourses = 2, prerequisites = [[1, 0]] → true
numCourses = 2, prerequisites = [[1, 0], [0, 1]] → false

LeetCode 207 · 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, DFS with path tracking

For each course, DFS tracking the current recursion path; if we hit a course already on the path, it’s a cycle.

from collections import defaultdict

def can_finish(num_courses, prerequisites):
    graph = defaultdict(list)
    for a, b in prerequisites:                   # L1: O(E) build adjacency list
        graph[b].append(a)

    def has_cycle(start):
        on_path = set()                          # L2: O(1) init per call
        def dfs(n):
            if n in on_path:                     # L3: O(1) membership check
                return True
            on_path.add(n)                       # L4: O(1)
            for nb in graph[n]:                  # L5: iterate neighbors
                if dfs(nb):                      # L6: recurse
                    return True
            on_path.remove(n)                    # L7: O(1) backtrack
            return False
        return dfs(start)

    for c in range(num_courses):                 # L8: call has_cycle for every node
        if has_cycle(c):
            return False
    return True

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
    const graph: number[][] = Array.from({ length: numCourses }, () => []);
    for (const [a, b] of prerequisites) {        // L1: O(E) build adjacency list
        graph[b].push(a);
    }

    function hasCycle(start: number): boolean {
        const onPath = new Set<number>();        // L2: O(1) init per call
        function dfs(n: number): boolean {
            if (onPath.has(n)) return true;      // L3: O(1) membership check
            onPath.add(n);                       // L4: O(1)
            for (const nb of graph[n]) {         // L5: iterate neighbors
                if (dfs(nb)) return true;        // L6: recurse
            }
            onPath.delete(n);                    // L7: O(1) backtrack
            return false;
        }
        return dfs(start);
    }

    for (let c = 0; c < numCourses; c++) {       // L8: call hasCycle for every node
        if (hasCycle(c)) return false;
    }
    return true;
}

func canFinish(numCourses int, prerequisites [][]int) bool {
    graph := make([][]int, numCourses)
    for _, p := range prerequisites {             // L1: O(E) build adjacency list
        graph[p[1]] = append(graph[p[1]], p[0])
    }

    var hasCycle func(start int) bool
    hasCycle = func(start int) bool {
        onPath := map[int]bool{}                  // L2: O(1) init per call
        var dfs func(n int) bool
        dfs = func(n int) bool {
            if onPath[n] { return true }          // L3: O(1) membership check
            onPath[n] = true                      // L4: O(1)
            for _, nb := range graph[n] {         // L5: iterate neighbors
                if dfs(nb) { return true }        // L6: recurse
            }
            delete(onPath, n)                     // L7: O(1) backtrack
            return false
        }
        return dfs(start)
    }

    for c := 0; c < numCourses; c++ {             // L8: call hasCycle for every node
        if hasCycle(c) { return false }
    }
    return true
}

final class Solution {
    func canFinish(_ numCourses: Int, _ prerequisites: [[Int]]) -> Bool {
        var graph = Array(repeating: [Int](), count: numCourses)
        for edge in prerequisites { graph[edge[0]].append(edge[1]) }
        func hasCycle(_ course: Int, _ path: inout Set<Int>) -> Bool {
            if path.contains(course) { return true }
            path.insert(course)
            for next in graph[course] where hasCycle(next, &path) { return true }
            path.remove(course)
            return false
        }
        for course in 0..<numCourses {
            var path = Set<Int>()
            if hasCycle(course, &path) { return false }
        }
        return true
    }
}

Where the time goes, line by line

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

Line	Per-call cost	Times executed	Contribution
L1 (build graph)	$O(1)$ per edge	E	$O(E)$
L8 (outer loop)	varies	V	V invocations of has_cycle
L3, L4, L7 (path ops)	$O(1)$	per node visited	-
L5, L6 (DFS traversal)	$O(V + E)$ per start	V	$O(V)$ calls × $O(V + E)$ each
L8 total	$O(V + E)$	V	$O(V² + VE)$ ← dominates

Because on_path is reset on every call to has_cycle, there is no memoization. A node reachable from k different starting points is fully re-explored k times. In a dense graph (E near V²), this blows up to $O(V³)$ .

Complexity

Time: $O(V² + VE)$ , driven by L8 (re-walking the graph from every node).
Space: $O(V + E)$ .

Correct but wasteful.

Approach 2: DFS with three-color cycle detection (optimal)

Each node is white (unvisited), gray (on the current DFS path), or black (finished). A gray-to-gray transition means a cycle.

from collections import defaultdict

def can_finish(num_courses, prerequisites):
    graph = defaultdict(list)
    for a, b in prerequisites:                   # L1: O(E) build graph
        graph[b].append(a)

    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * num_courses                # L2: O(V) init color array

    def dfs(n):
        if color[n] == GRAY:                     # L3: O(1) back-edge check
            return False   # cycle
        if color[n] == BLACK:                    # L4: O(1) already done
            return True
        color[n] = GRAY                          # L5: O(1) mark in-progress
        for nb in graph[n]:                      # L6: iterate neighbors
            if not dfs(nb):                      # L7: recurse
                return False
        color[n] = BLACK                         # L8: O(1) mark complete
        return True

    for c in range(num_courses):                 # L9: outer loop over all nodes
        if not dfs(c):
            return False
    return True

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

    const WHITE = 0, GRAY = 1, BLACK = 2;
    const color = new Array(numCourses).fill(WHITE);  // L2: O(V) init color array

    function dfs(n: number): boolean {
        if (color[n] === GRAY) return false;     // L3: O(1) back-edge check (cycle)
        if (color[n] === BLACK) return true;     // L4: O(1) already done
        color[n] = GRAY;                         // L5: O(1) mark in-progress
        for (const nb of graph[n]) {             // L6: iterate neighbors
            if (!dfs(nb)) return false;          // L7: recurse
        }
        color[n] = BLACK;                        // L8: O(1) mark complete
        return true;
    }

    for (let c = 0; c < numCourses; c++) {       // L9: outer loop over all nodes
        if (!dfs(c)) return false;
    }
    return true;
}

func canFinish(numCourses int, prerequisites [][]int) bool {
    graph := make([][]int, numCourses)
    for _, p := range prerequisites {             // L1: O(E) build graph
        graph[p[1]] = append(graph[p[1]], p[0])
    }
    const white, gray, black = 0, 1, 2
    color := make([]int, numCourses)              // L2: O(V) init color array

    var dfs func(n int) bool
    dfs = func(n int) bool {
        if color[n] == gray { return false }      // L3: back-edge check (cycle)
        if color[n] == black { return true }      // L4: already done
        color[n] = gray                           // L5: mark in-progress
        for _, nb := range graph[n] {             // L6: iterate neighbors
            if !dfs(nb) { return false }          // L7: recurse
        }
        color[n] = black                          // L8: mark complete
        return true
    }

    for c := 0; c < numCourses; c++ {             // L9: outer loop
        if !dfs(c) { return false }
    }
    return true
}

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

Where the time goes, line by line

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

Line	Per-call cost	Times executed	Contribution
L1 (build graph)	$O(1)$ per edge	E	$O(E)$
L2 (init colors)	$O(V)$	1	$O(V)$
L3, L4 (color checks)	$O(1)$	once per node entry	$O(V)$ total
L5, L8 (color transitions)	$O(1)$	each node goes WHITE→GRAY→BLACK once	$O(V)$ total
L6, L7 (edge traversal)	$O(1)$ per edge	each edge visited at most once	$O(E)$ ← dominates

The BLACK check at L4 is the memoization that makes this $O(V + E)$ instead of $O(V² + VE)$ . Once a node is colored BLACK, any future DFS that reaches it returns immediately without re-exploring its subtree.

Complexity

Time: $O(V + E)$ , driven by L6/L7 (each edge visited at most once across the whole run).
Space: $O(V + E)$ .

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
DFS from every node	$O(V² + VE)$	$O(V + E)$
DFS + three-color	$O(V + E)$	$O(V + E)$
Kahn’s algorithm (BFS)	$O(V + E)$	$O(V + E)$

Both DFS+color and Kahn’s are optimal. Kahn’s generalizes directly to problem 210 where we need the actual ordering, not just feasibility.

# Quick smoke tests, paste into a REPL or save as test_207.py and run.
# Uses the canonical implementation (Approach 2: DFS three-color).

from collections import defaultdict

def can_finish(num_courses, prerequisites):
    graph = defaultdict(list)
    for a, b in prerequisites:
        graph[b].append(a)

    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * num_courses

    def dfs(n):
        if color[n] == GRAY:
            return False
        if color[n] == BLACK:
            return True
        color[n] = GRAY
        for nb in graph[n]:
            if not dfs(nb):
                return False
        color[n] = BLACK
        return True

    for c in range(num_courses):
        if not dfs(c):
            return False
    return True

def _run_tests():
    # Example 1: simple chain, no cycle
    assert can_finish(2, [[1, 0]]) == True

    # Example 2: direct cycle
    assert can_finish(2, [[1, 0], [0, 1]]) == False

    # Edge: no prerequisites, trivially true
    assert can_finish(5, []) == True

    # Edge: single course, no prerequisites
    assert can_finish(1, []) == True

    # Larger cycle (3 nodes)
    assert can_finish(3, [[1, 0], [2, 1], [0, 2]]) == False

    # Larger DAG (no cycle)
    assert can_finish(4, [[1, 0], [2, 0], [3, 1], [3, 2]]) == True

    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
    const graph: number[][] = Array.from({ length: numCourses }, () => []);
    for (const [a, b] of prerequisites) graph[b].push(a);

    const WHITE = 0, GRAY = 1, BLACK = 2;
    const color = new Array(numCourses).fill(WHITE);

    function dfs(n: number): boolean {
        if (color[n] === GRAY) return false;
        if (color[n] === BLACK) return true;
        color[n] = GRAY;
        for (const nb of graph[n]) if (!dfs(nb)) return false;
        color[n] = BLACK;
        return true;
    }

    for (let c = 0; c < numCourses; c++) if (!dfs(c)) return false;
    return true;
}

console.assert(canFinish(2, [[1, 0]]) === true);
console.assert(canFinish(2, [[1, 0], [0, 1]]) === false);
console.assert(canFinish(5, []) === true);
console.assert(canFinish(1, []) === true);
console.assert(canFinish(3, [[1, 0], [2, 1], [0, 2]]) === false);
console.assert(canFinish(4, [[1, 0], [2, 0], [3, 1], [3, 2]]) === true);
console.log("all tests pass");

Graphs, cycle detection; topological sort
Hash Tables, adjacency list (defaultdict)

Cycle Detection, repeated-state tactics for finding loops in linked lists, graphs, arrays, and numeric processes.
Topological Sort, dependency-order tactics for DAGs, prerequisites, and detecting cycles in directed graphs.

207. Course Schedule (Medium)

Problem

Try it yourself

Approach 1: Brute force, DFS with path tracking

Approach 2: DFS with three-color cycle detection (optimal)

Summary

Test cases

Related data structures

Related concepts