Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Course Schedule
• 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 [a, b] means course b must be finished before course a.

The question is not asking for one specific order yet. It is asking whether some valid order exists at all.

That turns the problem into a graph question:

• each course is a node
• each prerequisite is a directed edge b -> a
• the schedule is possible if and only if that directed graph has no cycle

If a cycle exists, some course eventually depends on itself, directly or indirectly, so finishing everything is impossible.

The core insight

A directed acyclic graph has at least one node with no incoming edges. In this problem, that means at least one course currently has no unmet prerequisites and can be taken now.

That observation leads to a very practical strategy:

1. Find every course whose prerequisite count is 0.
2. Take those courses first.
3. Remove their outgoing edges, because finishing them satisfies requirements for later courses.
4. Repeat.

If this process removes all courses, the schedule is possible. If it gets stuck early, the remaining subgraph must contain a cycle.

This is Kahn’s algorithm for topological sorting.

Two optimal ways to solve it

There are two standard optimal solutions, both running in O(V + E) time:

• Topological sort with indegrees: repeatedly take courses with zero unmet prerequisites.
• DFS cycle detection: run depth-first search and detect whether the recursion path ever re-enters a node that is already being explored.

Both are correct because both are really testing the same property: whether the directed graph contains a cycle.

For interviews, the indegree approach is usually the easiest to explain operationally, so that is the implementation below.

How to derive the topological-sort approach

A clean derivation usually goes like this:

Start with small examples. For a chain like 0 -> 1 -> 2, course 0 is obviously safe to take first because nothing blocks it. After taking it, course 1 becomes safe, then course 2.

Now look at a cycle like 0 -> 1 -> 2 -> 0. No course is free at the start, because every node has at least one incoming edge. That is the signal that the schedule is impossible.

From those examples, the useful state becomes clear:

• for each course, keep the number of prerequisites not yet satisfied
• whenever that count reaches zero, the course becomes available

That is exactly enough information. There is no need to guess an order by backtracking, because every zero-indegree course is safe to process immediately.

Why this greedy process is safe

Taking a zero-indegree course can never create a new dependency problem.

Why? Because no unfinished course is required before it. So placing it next in the ordering cannot violate any prerequisite.

After taking it, the only thing that changes is that some other courses may now have one fewer unmet prerequisite. That means the algorithm only moves forward.

If the process ends before all courses are taken, then every remaining course still depends on another remaining course. In a finite directed graph, that implies a cycle.

Complexity

• Time: O(numCourses + len(prerequisites))
• Space: O(numCourses + len(prerequisites))

The graph must be built at least once, and each edge is processed once when its prerequisite course is completed.

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 the adjacency list and indegree counts.

    For each pair [course, prerequisite], add the directed edge:
    prerequisite -> course
    """
    outgoing_edges: list[list[int]] = [[] for _ in range(num_courses)]
    indegree_counts = [0] * num_courses

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

    return outgoing_edges, indegree_counts


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


def can_finish_all_courses(
    num_courses: int,
    prerequisites: Sequence[Sequence[int]],
) -> bool:
    """Return True when the prerequisite graph is acyclic."""
    outgoing_edges, indegree_counts = build_course_graph(
        num_courses,
        prerequisites,
    )
    available_courses = find_initial_available_courses(indegree_counts)
    completed_course_count = 0

    while available_courses:
        current_course = available_courses.popleft()
        completed_course_count += 1

        # Completing the current course satisfies one prerequisite for each
        # dependent course that points out of it.
        for dependent_course in outgoing_edges[current_course]:
            indegree_counts[dependent_course] -= 1

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

    return completed_course_count == num_courses


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

Why this implementation works

The invariant is:

• indegree_counts[x] always equals the number of prerequisites for course x that have not been completed yet

So whenever a course enters the queue, it is genuinely available to take next.

Each time the algorithm removes one course from the queue, it simulates completing that course and decreases the unmet-prerequisite count of every dependent course. If one of those counts hits zero, that dependent course is now unlocked and can be queued.

At the end, there are only two possibilities:

• every course was processed, so the graph had no cycle
• some courses were never processed, so they were trapped behind a cycle

That exactly matches the question the problem asks.

Interview follow-ups

What if the interviewer asks for the actual course order instead of just True or False?

That becomes the closely related topological-sorting problem. The same indegree-based algorithm still works, but instead of counting processed courses only, the solution stores them in an output list in the order they are popped from the queue.

If the final list has length numCourses, that list is a valid order. If it is shorter, a cycle blocked the remaining courses, so no valid order exists. The reason it works is unchanged: every course is appended only when all its prerequisites have already appeared earlier in the list. The complexity stays O(V + E), with the only extra cost being storing the output order.

How would you solve this with DFS instead?

The DFS version marks each node with one of three states: unvisited, visiting, or fully processed. During recursion, reaching a node that is already in the visiting state means the search has found a back edge, which is exactly a directed cycle.

This works because the visiting state represents the current recursion path. Re-entering that path means the graph has looped back before finishing a dependency chain. If DFS finishes every path without seeing that condition, the graph is acyclic. The time complexity is still O(V + E), and the space complexity is also O(V + E) overall if the adjacency list is counted, plus recursion-stack depth up to O(V). The tradeoff is that DFS is elegant for cycle detection, while Kahn’s algorithm is often more intuitive when the interviewer frames the problem as “keep taking available courses.”

What changes if duplicate prerequisite pairs are allowed?

The core logic still works, but the graph construction should treat duplicates carefully. If the input may contain repeated identical edges, blindly counting each one increases indegrees multiple times and can change the meaning of the problem unless duplicates are intended to count as separate constraints.

In most interview versions, duplicates are either disallowed or should be ignored as redundant information. In that case, the graph builder can keep a set of seen edges and only add each directed edge once. That preserves correctness because the real dependency relation is whether one course must precede another, not how many times the pair was listed. The tradeoff is a little extra memory during graph construction.

What if courses arrive over time and prerequisites can be updated dynamically?

Then the problem becomes much more like maintaining a changing dependency graph than solving a single static interview question. A simple recomputation after each update is still correct, but it can be expensive if updates are frequent.

In a production system, one might maintain indegrees, adjacency structures, and sometimes an incremental topological-order data structure. That is substantially more complex than the LeetCode version. The important tradeoff is between implementation simplicity and update efficiency: for one-shot inputs, the standard O(V + E) rebuild is the right answer; for high-frequency updates, more advanced dynamic graph techniques may be justified.

Practical takeaway

This problem becomes much easier once it is reframed from “Can I arrange courses somehow?” to “Does this directed graph contain a cycle?”

From there, the indegree method is almost mechanical:

• count prerequisites
• start with the courses that have none
• keep removing satisfied dependencies

That is the pattern worth remembering, because the same reasoning shows up again in build systems, task schedulers, package managers, and many other dependency-ordering problems.