LeetCode 207: Course Schedule Solution in Python Explained

Problem Statement

In LeetCode 207: Course Schedule, you’re given:

• numCourses: An integer representing the number of courses (0 to numCourses-1).
• prerequisites: A list of pairs [a, b], where course a requires course b to be completed first.
• Your task is to return true if all courses can be finished, false if there’s a cycle (impossible schedule).

This is a directed graph problem where edges represent dependencies. It differs from linked list reversal in LeetCode 206: Reverse Linked List, focusing instead on cycle detection in a graph.

Constraints

• 1 ≤ numCourses ≤ 2000.
• 0 ≤ prerequisites.length ≤ 5000.
• prerequisites[i].length == 2.
• 0 ≤ a, b < numCourses.
• All pairs are unique.

Examples

Let’s see some cases:

Copy codeInput: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: Course 1 requires Course 0. Schedule: 0 → 1.

Copy codeInput: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: Cycle: 1 → 0 → 1, impossible to finish.

Copy codeInput: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: true
Explanation: Schedule: 0 → 1 → 2 → 3.

These examples show we’re checking for a valid course order.

Understanding the Problem

How do we solve LeetCode 207: Course Schedule in Python? For numCourses = 2, prerequisites = [[1,0]], course 1 needs course 0—doable as 0 → 1. For [[1,0],[0,1]], there’s a cycle (1 → 0 → 1), making it impossible. This isn’t a string mapping problem like LeetCode 205: Isomorphic Strings; it’s about detecting cycles in a directed graph. We’ll use topological sorting: 1. Topological Sort with DFS: O(V + E) time, O(V) space—our best solution (V = vertices, E = edges). 2. Topological Sort with BFS: O(V + E) time, O(V) space—an alternative.

Let’s dive into the best solution.

Best Solution: Topological Sort with DFS Approach

Explanation

The Topological Sort with DFS approach detects cycles using depth-first search:

• Build an adjacency list from prerequisites (course → prerequisites).
• Use DFS to explore each course:
• Mark nodes as "visiting" (in progress) or "visited" (done).
• If we revisit a "visiting" node, there’s a cycle (false).
• If all nodes are explored without cycles, return true.

This runs in O(V + E) time (visit each vertex and edge once) and O(V) space (recursion stack and sets), making it efficient and clear—our best solution.

For [[1,0]], it confirms a valid order; for [[1,0],[0,1]], it detects the cycle.

Step-by-Step Example

Example 1: numCourses = 2, prerequisites = [[1,0]]

Goal: Return true.

• Step 1: Build graph.
• graph = {0: [], 1: [0]{ (1 depends on 0).
• Step 2: Initialize.
• visiting = set(), visited = set().
• Step 3: DFS on each course.
• course = 0:
• Not visiting/visited, add to visiting.
• No prerequisites, remove from visiting, add to visited.
• course = 1:
• Add to visiting, check 0.
• 0 in visited, no cycle.
• Remove 1 from visiting, add to visited.
• Step 4: Finish.
• No cycles, return true.

Example 2: numCourses = 2, prerequisites = [[1,0],[0,1]]

Goal: Return false.

• Step 1: graph = {0: [1], 1: [0]{.
• Step 2: visiting = set(), visited = set().
• Step 3:
• course = 0:
• Add to visiting, check 1.
• 1 not visited, recurse on 1.
• 1: Add to visiting, check 0.
• 0 in visiting, cycle detected, return false.
• Output: false.

How the Code Works (Topological Sort with DFS) – Detailed Line-by-Line Explanation

Here’s the Python code with a detailed breakdown:

Copy codefrom collections import defaultdict

def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    # Line 1: Build adjacency list
    graph = defaultdict(list)
    # Default dict for graph (e.g., {{)
    for course, prereq in prerequisites:
        # Iterate pairs (e.g., [1,0])
        graph[course].append(prereq)
        # Add edge (e.g., 1: [0])

    # Line 2: Initialize tracking sets
    visiting = set()
    # Nodes in current DFS path (e.g., set())
    visited = set()
    # Nodes fully explored (e.g., set())

    # Line 3: DFS helper function
    def dfs(course: int) -> bool:
        # Check if course can be completed
        if course in visiting:
            # Cycle detected (e.g., 0 in visiting)
            return False
        if course in visited:
            # Already processed, no cycle (e.g., 0 in visited)
            return True

        visiting.add(course)
        # Mark as being explored (e.g., add 1)
        for prereq in graph[course]:
            # Check each prerequisite (e.g., 0)
            if not dfs(prereq):
                # If any prereq has a cycle (e.g., false)
                return False

        visiting.remove(course)
        # Done exploring (e.g., remove 1)
        visited.add(course)
        # Mark as completed (e.g., add 1)
        return True

    # Line 4: Check all courses
    for course in range(numCourses):
        # Iterate 0 to numCourses-1 (e.g., 0, 1)
        if course not in visited:
            # Only process unvisited (e.g., 0)
            if not dfs(course):
                # If cycle found (e.g., false)
                return False

    # Line 5: No cycles found
    return True
    # All courses can be finished (e.g., true)

This solution elegantly detects cycles using DFS.

Alternative: Topological Sort with BFS Approach

Explanation

The Topological Sort with BFS approach uses in-degree counting:

• Build a graph and track in-degrees (number of prerequisites per course).
• Start with courses having 0 in-degree (no prerequisites).
• Use a queue to process nodes, reducing in-degrees of dependents.
• If all courses are processed, return true; otherwise, a cycle exists (false).

It’s O(V + E) time and O(V) space, offering a level-order alternative.

Step-by-Step Example

For numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]:

• Graph: 0: [], 1: [0], 2: [0], 3: [1,2].
• In-degrees: 0:0, 1:1, 2:1, 3:2.
• Queue: [0], processed = 0.
• 0: Reduce 1, 2 to 0, queue: [1,2], processed = 1.
• 1: Reduce 3 to 1, processed = 2.
• 2: Reduce 3 to 0, queue: [3], processed = 3.
• 3: Processed = 4, matches numCourses.
• Output: true.

How the Code Works (BFS)

Copy codefrom collections import defaultdict, deque

def canFinishBFS(numCourses: int, prerequisites: list[list[int]]) -> bool:
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1

    queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
    processed = 0

    while queue:
        curr = queue.popleft()
        processed += 1
        for next_course in graph[curr]:
            in_degree[next_course] -= 1
            if in_degree[next_course] == 0:
                queue.append(next_course)

    return processed == numCourses

Complexity

• Topological Sort with DFS:
• Time: O(V + E) – visit each vertex and edge.
• Space: O(V) – sets and stack.
• Topological Sort with BFS:
• Time: O(V + E) – process each vertex and edge.
• Space: O(V) – queue and in-degree array.

Efficiency Notes

Topological Sort with DFS is our best solution for its clarity and flexibility (can be adapted to find the order). BFS is equally efficient and intuitive for dependency resolution.

Key Insights

• Cycle: Prevents completion.
• DFS: Detects cycles via recursion.
• BFS: Processes level by level.

Additional Example

For numCourses = 3, [[1,0],[2,1]]:

• DFS/BFS: 0 → 1 → 2, true.

Edge Cases

• No prerequisites: true.
• Single course: true.
• All dependent: [[0,1],[1,0]], false.

Both handle these well.

Final Thoughts

LeetCode 207: Course Schedule in Python is a fantastic graph problem. Topological Sort with DFS offers depth and clarity, while BFS provides a queue-based alternative. Want more? Try LeetCode 210: Course Schedule II or LeetCode 200: Number of Islands. Test your skills—Solve LeetCode 207 on LeetCode with numCourses = 2, prerequisites = [[1,0]] (expecting true)—schedule those courses today!