Course Schedule II medium

Problem Statement

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Example 1:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] Output: [0,1,2,3] or [0,2,1,3] Explanation: There are a total of 4 courses to take. To take course 1 you should have finished course 0, and to take course 2 you should also have finished course 0. Finally, to take course 3 you should have finished both courses 1 and 2. Both the output sequences are valid.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0]] Output: [0,1] Explanation: To take course 1 you should have finished course 0. So the correct course order is [0,1].

Steps:

1. Build the graph: Represent the courses and their prerequisites as a directed graph. Each course is a node, and a directed edge from course b to course a indicates that b is a prerequisite for a.
2. Find in-degrees: Calculate the in-degree of each node (the number of incoming edges). This represents the number of prerequisites for each course.
3. Topological Sort: Use a topological sort algorithm (like Kahn's algorithm) to find a valid course order. This algorithm prioritizes nodes with zero in-degree (no prerequisites).
4. Handle cycles: If a cycle is detected (meaning there's no valid order), return an empty array.

Explanation:

Kahn's algorithm for topological sort works as follows:

1. Initialize a queue with all nodes (courses) having an in-degree of 0.
2. While the queue is not empty:
   • Dequeue a node. This node can be taken next.
   • Add the dequeued node to the result list.
   • For each neighbor (course that depends on the dequeued course):
     • Decrement its in-degree.
     • If its in-degree becomes 0, add it to the queue.
3. If the length of the result list equals the number of courses, a valid order was found. Otherwise, there's a cycle.

Code:

from collections import defaultdict, deque

def findOrder(numCourses, prerequisites):
    """
    Finds a topological ordering of courses.

    Args:
        numCourses: The total number of courses.
        prerequisites: A list of prerequisites, where each element is a pair [ai, bi] indicating that course bi must be taken before course ai.

    Returns:
        A list representing a valid course order, or an empty list if it's impossible to finish all courses.
    """

    graph = defaultdict(list)  # Adjacency list to represent the graph
    in_degree = [0] * numCourses  # Array to store in-degrees of each course

    # Build the graph and calculate in-degrees
    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1

    queue = deque()
    # Add courses with in-degree 0 to the queue
    for i in range(numCourses):
        if in_degree[i] == 0:
            queue.append(i)

    result = []
    while queue:
        course = queue.popleft()
        result.append(course)
        for neighbor in graph[course]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

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

Complexity:

• Time Complexity: O(V + E), where V is the number of courses (vertices) and E is the number of prerequisites (edges). This is because we visit each vertex and edge once.
• Space Complexity: O(V + E) to store the graph and in-degree array. The queue also takes space proportional to the number of vertices in the worst case.