Coding interview problems › Graphs & Grids

🗺️ Graphs & Grids Medium

Course Schedule II

Course Schedule II explained: return a valid course order with Kahn's topological sort, or an empty list on a cycle. Tested Python code and a live visual.

Also searched as: find a valid course order · topological sort order with Kahn's algorithm

🗂️

Try it live Free

Topological Sort

Step through the Topological Sort lab and read off the order in which courses leave the queue: that sequence is the answer this problem asks for.

Open the playground →

The problem

Same setup as Course Schedule: n courses and pairs [a, b] meaning b must come before a. Return any order in which you can take all the courses, or an empty list if it is impossible.

Inputn = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output[0, 1, 2, 3] (or [0, 2, 1, 3])

Several orders are valid.

The key insight

Kahn's algorithm already produces the order: the sequence in which courses become unblocked and leave the queue is a topological order. If some courses never reach in-degree 0, they sit on a cycle and no valid order exists.

Brute force first: Generating permutations and testing each against every prerequisite is O(n!·E).

Step-by-step approach

  1. Build the graph pre -> course and the in-degree array.
  2. Queue every course with in-degree 0.
  3. Pop a course and append it to the order.
  4. Decrement the in-degree of its dependants and queue any that reach 0.
  5. If the order has n courses return it; otherwise return [].

Python solution

PYTHON 3tested
from collections import deque


def find_order(num_courses, prerequisites):
    graph = [[] for _ in range(num_courses)]
    indeg = [0] * num_courses
    for course, pre in prerequisites:
        graph[pre].append(course)
        indeg[course] += 1
    q = deque(c for c in range(num_courses) if indeg[c] == 0)
    order = []
    while q:
        c = q.popleft()
        order.append(c)                # c's prerequisites are all done
        for nxt in graph[c]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                q.append(nxt)
    return order if len(order) == num_courses else []

Complexity

TimeO(V + E)
SpaceO(V + E)

Each course enters and leaves the queue once and each edge decrements one in-degree once. The graph and the order list are linear in size.

Common mistakes

Frequently asked questions

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

O(V + E) time and space for V courses and E prerequisite pairs.

Is the topological order unique?

Only when the graph forces a single chain. Usually several orders are valid, and any of them is accepted. Using a min-heap instead of a queue gives the lexicographically smallest order.

How does the DFS version produce an order?

Add each node to a list after all its dependants finish (post-order), then reverse the list. A node seen again while still on the current path signals a cycle.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Graphs & Grids Graph Search: BFS vs DFS lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.