LeetCode 210: Course Schedule II Solution in Python Explained

Problem Statement

In LeetCode 210: Course Schedule II, 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 an array of course IDs in a valid order to finish all courses, or an empty array if there’s a cycle.

This extends LeetCode 207: Course Schedule by requiring the actual order, not just feasibility. It’s a directed graph problem where we need a topological sort.

Constraints

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

Examples

Let’s see some cases:

Copy codeInput: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: Course 1 requires Course 0, so order is 0 → 1.

Copy codeInput: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: Valid orders exist, e.g., 0 → 1 → 2 → 3.

Copy codeInput: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: []
Explanation: Cycle (1 → 0 → 1), no valid order.

These examples show we’re finding a topological order or detecting impossibility.

Understanding the Problem

How do we solve LeetCode 210: Course Schedule II in Python? For numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]], we need an order like [0,1,2,3]—course 0 first, then 1 and 2 (in any order), then 3. A cycle like [[1,0],[0,1]] makes it impossible. This isn’t a subarray problem like LeetCode 209: Minimum Size Subarray Sum; it’s about ordering a directed acyclic graph (DAG). We’ll use: 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 builds the order by exploring the graph:

• Build an adjacency list from prerequisites (course → prerequisites).
• Use DFS with cycle detection:
• Track "visiting" (in progress) and "visited" (done) nodes.
• If a cycle is detected, return an empty list.
• Post-order DFS adds courses to the result after exploring prerequisites.
• Reverse the post-order to get the topological order.

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

For [[1,0]], it returns [0,1]; for [[1,0],[0,1]], it detects a cycle.

Step-by-Step Example

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

Goal: Return [0,1,2,3] (or valid variant).

• Step 1: Build graph.
• graph = {0: [], 1: [0], 2: [0], 3: [1,2]{.
• Step 2: Initialize.
• visiting = set(), visited = set(), order = [].
• Step 3: DFS on each course.
• course = 0:
• Add to visiting, no prerequisites, remove from visiting, add to visited, append 0.
• order = [0].
• course = 1:
• Add to visiting, check 0 (visited), append 1.
• order = [0,1].
• course = 2:
• Add to visiting, check 0 (visited), append 2.
• order = [0,1,2].
• course = 3:
• Add to visiting, check 1, 2 (visited), append 3.
• order = [0,1,2,3].
• Step 4: Finish.
• No cycles, reverse order (optional here), return [0,1,2,3].

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

Goal: Return [].

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

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 findOrder(numCourses: int, prerequisites: list[list[int]]) -> list[int]:
    # 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 and order
    visiting = set()
    # Nodes in current DFS path (e.g., set())
    visited = set()
    # Nodes fully explored (e.g., set())
    order = []
    # Resulting course order (e.g., [])

    # Line 3: DFS helper function
    def dfs(course: int) -> bool:
        # Build topological order or detect cycle
        if course in visiting:
            # Cycle detected (e.g., 0 in visiting)
            return False
        if course in visited:
            # Already processed (e.g., 0 in visited)
            return True

        visiting.add(course)
        # Mark as being explored (e.g., add 1)
        for prereq in graph[course]:
            # Check prerequisites (e.g., 0)
            if not dfs(prereq):
                # Cycle in prereq (e.g., false)
                return False

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

    # Line 4: Process all courses
    for course in range(numCourses):
        # Iterate 0 to numCourses-1 (e.g., 0 to 3)
        if course not in visited:
            # Only process unvisited (e.g., 0)
            if not dfs(course):
                # Cycle found (e.g., false)
                return []

    # Line 5: Return valid order
    return order
    # Topological order (e.g., [0,1,2,3])

This solution builds the order while ensuring no cycles.

Alternative: Topological Sort with BFS Approach

Explanation

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

• Build a graph and track in-degrees (prerequisites per course).
• Queue courses with 0 in-degree.
• Process nodes, reducing in-degrees, adding to order.
• If all courses are processed, return the order; otherwise, return [].

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], order = [].
• 0: order = [0], reduce 1, 2 to 0, queue: [1,2].
• 1: order = [0,1], reduce 3 to 1.
• 2: order = [0,1,2], reduce 3 to 0, queue: [3].
• 3: order = [0,1,2,3].
• Output: [0,1,2,3].

How the Code Works (BFS)

Copy codefrom collections import defaultdict, deque

def findOrderBFS(numCourses: int, prerequisites: list[list[int]]) -> list[int]:
    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])
    order = []

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

    return order if len(order) == numCourses else []

Complexity

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

Efficiency Notes

Topological Sort with DFS is our best solution for its clarity and direct order-building. BFS is equally efficient and often preferred for its queue-based simplicity.

Key Insights

• Topological Order: Prerequisite-first.
• Cycle: Blocks completion.
• DFS vs BFS: Depth vs breadth.

Additional Example

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

• DFS/BFS: [0,1,2].

Edge Cases

• No prerequisites: Any order of [0,1,...,n-1].
• Single course: [0].
• Cycle: [[0,1],[1,0]] → [].

Both handle these well.

Final Thoughts

LeetCode 210: Course Schedule II in Python is a rewarding graph challenge. Topological Sort with DFS offers depth and elegance, while BFS provides a straightforward alternative. Want more? Try LeetCode 207: Course Schedule or LeetCode 269: Alien Dictionary. Test your skills—Solve LeetCode 210 on LeetCode with numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] (expecting [0,1,2,3])—order those courses today!