Course Schedule

PracticeNeetCode ↗LeetCode ↗

There are numCourses courses labeled 0 to numCourses - 1. Given prerequisite pairs [a, b] meaning a requires b first, return whether it's possible to finish every course.

Example

Key Pointers

• This is cycle detection in a directed graph — a cycle in the prerequisite graph means no valid course order exists.
• DFS with a "currently on this path" set catches cycles: revisiting a course still on the current recursion path means a cycle was found.
• Once a course is confirmed cycle-free, memoize it so it isn't re-verified every time it shows up as someone else's prerequisite.

Step-by-Step Analysis

1. Build an adjacency list mapping each course to its list of prerequisites.
2. Keep a visiting set (nodes on the current DFS path) and a visited set (nodes already confirmed safe).
3. DFS(course): if it's in visiting, return False (cycle). If it's in visited, return True. Otherwise mark it visiting, recurse into every prerequisite, then move it from visiting to visited and return True.
4. Run DFS across every course; return False the moment any call reports a cycle, otherwise return True.

Complexity

Time: O(V + E) — Space: O(V + E)

Code

def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    graph = {i: [] for i in range(numCourses)}
    for course, pre in prerequisites:
        graph[course].append(pre)

    visiting, visited = set(), set()

    def dfs(course: int) -> bool:
        if course in visiting:
            return False
        if course in visited:
            return True

        visiting.add(course)
        for pre in graph[course]:
            if not dfs(pre):
                return False
        visiting.remove(course)
        visited.add(course)
        return True

    return all(dfs(course) for course in range(numCourses))

Code Explanation

How the solution above works, piece by piece.

1. Build graph[course] = list of its prerequisites.
2. visiting holds courses on the current DFS path; visited holds courses already proven completable.
3. Entering a course that is in visiting means a cycle → False. A course already in visited is fine → True without re-checking.
4. Otherwise mark it visiting, check every prerequisite, then move it from visiting to visited.
5. all(dfs(course) ...) checks every course (the graph may be disconnected). O(V + E).

Visual Walkthrough

Running it on numCourses = 2, prerequisites = [[1, 0], [0, 1]]:

Video Explanation

NeetCode — Course Schedule, LeetCode 207