Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Course Schedule II
• Main tags: Depth-First Search, Breadth-First Search, Graph Theory, Topological Sort

What the problem is really asking

There are numCourses courses labeled from 0 to numCourses - 1.

Each prerequisite pair [course, prerequisite] means the prerequisite must be taken before the course. The task is to return any valid order that takes every course, or return an empty list when no such order exists.

This is a dependency-ordering problem. Model each course as a graph node and each prerequisite pair as a directed edge:

prerequisite -> course

Now the question becomes: can this directed graph be arranged so every edge points from an earlier course to a later course? That arrangement is called a topological order. It exists exactly when the graph has no directed cycle.

The core idea

A course with zero unmet prerequisites is always safe to take next. It does not depend on any remaining course, so placing it in the answer cannot violate the rules.

After taking that course, every course that depends on it has one fewer unmet prerequisite. Some of those dependent courses may now become available too.

This leads to Kahn’s algorithm:

1. Count how many prerequisites each course still needs.
2. Put every zero-prerequisite course in a queue.
3. Repeatedly take one available course, append it to the answer, and relax its outgoing edges.
4. If the answer contains every course, return it. Otherwise, a cycle blocked the remaining courses, so return [].

How to derive it in an interview

Start from the requirement for a valid answer: every prerequisite must appear before the course that depends on it. That means the first course in any valid answer must have no prerequisites inside the graph. If every remaining course has at least one prerequisite, there is no possible first move unless the graph has already been reduced by previous choices.

So the algorithm should not guess. It should repeatedly choose from the courses that are provably available right now. The only state needed to know that is each course’s indegree, which is the number of incoming prerequisite edges that have not been satisfied yet.

When a zero-indegree course is removed, the algorithm is effectively saying, “this course is finished.” Each outgoing edge from that course can then be removed from consideration, which may unlock more courses. If this process gets stuck before all courses are taken, the leftover courses must depend on one another in a cycle.

Python solution

from collections import deque
from typing import Sequence


def build_course_graph(
    num_courses: int,
    prerequisites: Sequence[Sequence[int]],
) -> tuple[list[list[int]], list[int]]:
    """
    Build a directed graph and indegree array.

    For every pair [course, prerequisite], the directed edge is:
    prerequisite -> course
    """
    next_courses: list[list[int]] = [[] for _ in range(num_courses)]
    unmet_prerequisite_counts = [0] * num_courses

    for course, prerequisite in prerequisites:
        next_courses[prerequisite].append(course)
        unmet_prerequisite_counts[course] += 1

    return next_courses, unmet_prerequisite_counts


def find_available_courses(
    unmet_prerequisite_counts: Sequence[int],
) -> deque[int]:
    """Return all courses that currently have no unmet prerequisites."""
    return deque(
        course
        for course, unmet_count in enumerate(unmet_prerequisite_counts)
        if unmet_count == 0
    )


def find_course_order(
    num_courses: int,
    prerequisites: Sequence[Sequence[int]],
) -> list[int]:
    """
    Return one valid ordering of all courses, or [] when a cycle exists.

    The algorithm is Kahn's topological sort. Each course enters the output
    only after all of its prerequisite courses have already been processed.
    """
    next_courses, unmet_prerequisite_counts = build_course_graph(
        num_courses,
        prerequisites,
    )
    available_courses = find_available_courses(unmet_prerequisite_counts)
    course_order: list[int] = []

    while available_courses:
        current_course = available_courses.popleft()
        course_order.append(current_course)

        # Completing current_course satisfies one prerequisite for each
        # course that directly depends on it.
        for dependent_course in next_courses[current_course]:
            unmet_prerequisite_counts[dependent_course] -= 1

            if unmet_prerequisite_counts[dependent_course] == 0:
                available_courses.append(dependent_course)

    if len(course_order) != num_courses:
        return []

    return course_order


class Solution:
    def findOrder(
        self,
        numCourses: int,
        prerequisites: list[list[int]],
    ) -> list[int]:
        """LeetCode entry point."""
        return find_course_order(numCourses, prerequisites)

Why this works

The key invariant is:

unmet_prerequisite_counts[course] always equals the number of prerequisites for course that have not appeared in the output yet.

At the start, this is true because the algorithm counts every incoming edge. When a course is appended to the output, every outgoing edge from that course represents one prerequisite that has just been satisfied, so the algorithm decrements the dependent course’s count.

A course is added to the queue only when its count becomes zero. Therefore, every course appended to course_order has all of its prerequisites earlier in the same list.

If all courses are appended, the returned list is a valid topological order. If some courses are missing, the queue became empty while those courses still had unmet prerequisites. In a finite directed graph, that can only happen when the remaining courses contain a directed cycle, so no valid order exists.

The time complexity is O(numCourses + len(prerequisites)) because each course is queued at most once and each prerequisite edge is processed once. The space complexity is also O(numCourses + len(prerequisites)) for the graph, indegree counts, queue, and output list.

Interview follow-ups

How would you solve it with DFS instead?

Use three states for each course: unvisited, visiting, and visited. During DFS, mark a course as visiting when it enters the current recursion path. If the search reaches another visiting course, it has found a directed cycle, so no schedule is possible.

When DFS finishes exploring all descendants of a course, mark it visited and append it to an output list. Because descendants are appended before the current course, the final output must be reversed to become a valid prerequisite-before-course ordering.

This works because DFS postorder naturally puts a node after everything reachable from it. With edges prerequisite -> course, reversing postorder makes prerequisites appear before dependent courses. The time and space complexities remain O(V + E), though recursion depth can be O(V) and may matter in Python for very deep graphs.

What if the interviewer asks whether the course order is unique?

The order is unique only if there is exactly one available zero-indegree course at every step of Kahn’s algorithm. If the queue ever contains two or more courses, either one can be placed next without violating prerequisites, so multiple valid orders exist.

This test works because a zero-indegree course has no unmet dependency on any other remaining course. When two such courses exist, swapping their relative order still keeps all prerequisite edges valid. The complexity does not change, but the implementation must check the queue size before each pop.

How would you return the lexicographically smallest valid order?

Replace the FIFO queue with a min-heap of available courses. Whenever several courses are currently available, pop the smallest course number first.

This works because the only courses eligible for the next position are the zero-indegree courses. Choosing the smallest among them makes the earliest possible position as small as it can be without breaking any prerequisite constraint. The tradeoff is that queue operations become O(log V), so the runtime becomes O((V + E) log V) instead of linear.

What if duplicate prerequisite pairs appear in the input?

If duplicates are meant to be redundant, the graph builder should ignore repeated edges by tracking a seen_edges set before incrementing indegrees. Otherwise, a repeated pair would count the same dependency more than once, which can make the implementation’s bookkeeping disagree with the real course relationship.

Ignoring duplicates preserves the meaning of the problem because a course either requires another course or it does not. The tradeoff is extra memory for the edge set during graph construction, but the topological-sort logic stays the same.

How would you handle a streaming system where courses or prerequisites are added later?

For occasional updates, the simplest correct approach is to rebuild the graph and rerun topological sort after each update. That keeps the implementation easy to reason about and still costs only O(V + E) per recomputation.

For frequent updates, this becomes a dynamic graph problem. A production system may maintain adjacency lists, indegrees, and an existing topological order, then update only the affected region when a new edge arrives. That can be faster, but it is much harder to implement correctly, especially when a new edge may introduce a cycle.

Practical takeaway

Course Schedule II is the “return the ordering” version of cycle detection in a dependency graph. The most practical pattern is to keep an indegree count, repeatedly take courses with no unmet prerequisites, and verify that every course made it into the result.

Once that idea is clear, the implementation is straightforward: build prerequisite -> course edges, process zero-indegree courses, and return an empty list only when a cycle prevents a complete ordering.