Course Schedule II – Solution & Complexity

Q: What is the time and space complexity of Course Schedule II?

The optimal Course Schedule II solution runs in `O(V + E)` time and `O(V + E)` space. Kahn topological sort removes zero-indegree courses and appends them to the answer order.

Q: What is the most efficient way to solve Course Schedule II?

Kahn topological sort removes zero-indegree courses and appends them to the answer order. This gives `O(V + E)` time complexity, and is a classic graph, topological sort, and breadth first search problem.

Q: How do you solve Course Schedule II in Python, JavaScript, Java, Go, Rust, C++ & Ruby?

We provide a worked Course Schedule II solution in Python, JavaScript, Java, Go, Rust, C++ & Ruby with a step-by-step explanation above. You can also open the interactive editor to write and run your own Python solution against the test cases in the browser.

Q: Is Course Schedule II an easy or hard interview question?

Course Schedule II is generally rated **Medium**. It tests graph, topological sort, and breadth first search, which are common coding-interview patterns.

Solution Walkthrough

1. Recognize the graph problem

Every course is a vertex and every prerequisite pair is a directed edge.
We need a topological ordering: every prerequisite must appear before the course that depends on it.

2. Brute-force by repeatedly scanning prerequisites

In each round, search for courses whose prerequisites are already taken.
This is correct but can revisit the full prerequisite list many times, giving roughly O(V * E) work.

def find_order(numCourses, prerequisites):
    taken = [False] * numCourses
    order = []
    while len(order) < numCourses:
        progress = False
        for course in range(numCourses):
            if taken[course]:
                continue
            ready = True
            for target, prerequisite in prerequisites:
                if target == course and not taken[prerequisite]:
                    ready = False
                    break
            if ready:
                taken[course] = True
                order.append(course)
                progress = True
        if not progress:
            return []
    return order

3. Use indegrees to avoid repeated rescans

Precompute each course's indegree and adjacency list once.
Then each edge is processed exactly once when its prerequisite is removed from the queue.

4. Run Kahn's algorithm with a FIFO queue

Seed the queue with every course whose indegree is zero.
Pop courses, append them to the answer, and decrement the indegree of their outgoing neighbors.

def find_order(numCourses, prerequisites):
    graph = [[] for _ in range(numCourses)]
    indegree = [0] * numCourses
    for course, prerequisite in prerequisites:
        graph[prerequisite].append(course)
        indegree[course] += 1
    queue = [course for course in range(numCourses) if indegree[course] == 0]
    head = 0
    order = []
    while head < len(queue):
        course = queue[head]
        head += 1
        order.append(course)
        for nxt in graph[course]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)
    return order if len(order) == numCourses else []

5. Dry run / queue trace

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

step	queue before pop	popped	indegree updates	order
start	`[0]`	-	indegrees = `[0,2,1,1]`	`[]`
1	`[0]`	`0`	`1 -> 1`, `2 -> 0`, enqueue `2`	`[0]`
2	`[0,2]`	`2`	`1 -> 0`, enqueue `1`	`[0,2]`
3	`[0,2,1]`	`1`	`3 -> 0`, enqueue `3`	`[0,2,1]`
4	`[0,2,1,3]`	`3`	none	`[0,2,1,3]`

Every course appears exactly once, so the graph is acyclic and the built order is valid.

6. Final solution and complexity

Kahn's algorithm processes each course and prerequisite edge once, giving O(V + E) time with O(V + E) graph storage.

def find_order(numCourses: int, prerequisites: list[list[int]]) -> list[int]:
    graph = [[] for _ in range(numCourses)]
    indegree = [0] * numCourses
    for course, prerequisite in prerequisites:
        graph[prerequisite].append(course)
        indegree[course] += 1
    queue = [course for course in range(numCourses) if indegree[course] == 0]
    head = 0
    order: list[int] = []
    while head < len(queue):
        course = queue[head]
        head += 1
        order.append(course)
        for nxt in graph[course]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)
    return order if len(order) == numCourses else []

Course Schedule II – Solution & Complexity

Solution Walkthrough

1. Recognize the graph problem

2. Brute-force by repeatedly scanning prerequisites

3. Use indegrees to avoid repeated rescans

4. Run Kahn's algorithm with a FIFO queue

5. Dry run / queue trace

6. Final solution and complexity

FAQ

What is the time and space complexity of Course Schedule II?

What is the most efficient way to solve Course Schedule II?

How do you solve Course Schedule II in Python, JavaScript, Java, Go, Rust, C++ & Ruby?

Is Course Schedule II an easy or hard interview question?

See also