Course Schedule II

You are given a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are also given an array prerequisites where prerequisites[i] = [a<sub>i</sub>, b<sub>i</sub>] indicates that you must take course b<sub>i</sub> first if you want to take course a<sub>i</sub>.

• 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 = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].

Example 2:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

Example 3:

Input: numCourses = 1, prerequisites = []
Output: [0]

from collections import defaultdict

def findOrder(numCourses: int, prerequisites: list[list[int]]) -> list[int]:
    # Build the graph and in-degree array
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for course, pre in prerequisites:
        graph[pre].append(course)
        in_degree[course] += 1

    # Add courses with in-degree 0 to the queue
    queue = [i for i in range(numCourses) if in_degree[i] == 0]
    
    # Perform topological sort
    result = []
    while queue:
        course = queue.pop(0)
        result.append(course)

        for next_course in graph[course]:
            in_degree[next_course] -= 1
            if in_degree[next_course] == 0:
                queue.append(next_course)

    # Check for cycle
    if len(result) == numCourses:
        return result
    else:
        return []


# Example Usage
numCourses = 4
prerequisites = [[1,0],[2,0],[3,1],[3,2]]
print(findOrder(numCourses, prerequisites))
# Output: [0, 1, 2, 3] or [0, 2, 1, 3]

numCourses = 2
prerequisites = [[1,0]]
print(findOrder(numCourses, prerequisites))
# Output: [0, 1]

numCourses = 1
prerequisites = []
print(findOrder(numCourses, prerequisites))
# Output: [0]

numCourses = 2
prerequisites = [[0,1],[1,0]]
print(findOrder(numCourses, prerequisites))
# Output: []

Explanation:

The problem requires us to find a valid ordering of courses given a set of prerequisites. If it's impossible to finish all courses due to cycles in the prerequisites, we should return an empty array. This is a classic topological sorting problem, which can be solved using Kahn's algorithm.

1. Build the Graph: Represent the courses and prerequisites as a directed graph, where each course is a node, and each prerequisite is a directed edge from the prerequisite course to the course that depends on it.
2. Calculate In-Degrees: Compute the in-degree of each course, which is the number of prerequisites it has. Courses with an in-degree of 0 are courses that can be taken immediately.
3. Topological Sort:
   • Add all courses with an in-degree of 0 to a queue.
   • While the queue is not empty, remove a course from the queue and add it to the result.
   • For each neighbor of the removed course (i.e., courses that depend on it), reduce their in-degree by 1. If any neighbor's in-degree becomes 0, add it to the queue.
4. Cycle Detection: After the topological sort, if the number of courses in the result is equal to the total number of courses, it means there are no cycles, and we have found a valid ordering. Otherwise, there is a cycle, and it is impossible to finish all courses.

Big O Analysis:

• Time Complexity: O(V + E), where V is the number of courses (vertices) and E is the number of prerequisites (edges). Building the graph and calculating in-degrees takes O(E) time. The topological sort visits each vertex and edge once, taking O(V + E) time.
• Space Complexity: O(V + E). The graph is stored using an adjacency list, which takes O(V + E) space. The in-degree array takes O(V) space. The queue and result list take O(V) space in the worst case.