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

Step 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.

Step 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

Step 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.

Step 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 []

Step 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.

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]`

Step 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

Step 1: Recognize the graph problem

Step 2: Brute-force by repeatedly scanning prerequisites

Step 3: Use indegrees to avoid repeated rescans

Step 4: Run Kahn's algorithm with a FIFO queue

Step 5: Dry run / queue trace

Step 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

Course Schedule II – Solution & Complexity

Solution Walkthrough

1Step 1: Recognize the graph problem

2Step 2: Brute-force by repeatedly scanning prerequisites

3Step 3: Use indegrees to avoid repeated rescans

4Step 4: Run Kahn's algorithm with a FIFO queue

5Step 5: Dry run / queue trace

6Step 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

Step 1: Recognize the graph problem

Step 2: Brute-force by repeatedly scanning prerequisites

Step 3: Use indegrees to avoid repeated rescans

Step 4: Run Kahn's algorithm with a FIFO queue

Step 5: Dry run / queue trace

Step 6: Final solution and complexity