Course Schedule II

The problem of finding the order of courses with given prerequisites can be solved using topological sorting. We can model the courses and prerequisites as a directed graph where nodes represent courses, and a directed edge from course A to course B means that A is a prerequisite for B.

Here’s a step-by-step explanation to find the correct order of courses:

1. Create a Graph: Represent the courses and prerequisites as a directed graph. Use an adjacency list to store the edges.

2. Calculate In-Degrees: In-degree of a node is the number of prerequisites for a course. It represents how many courses need to be completed before taking that course.

3. Find Starting Points: Courses with an in-degree of 0 can be taken immediately, as they have no prerequisites.

4. Topological Sort: a. Add all the nodes with in-degree 0 to a queue. b. Remove a node from the queue, add it to the result, and reduce the in-degree of its neighbors by 1. c. If the in-degree of a neighbor becomes 0, add it to the queue. d. Repeat until the queue is empty.

5. Check for Cycles: If there’s a cycle in the graph, some courses can’t be taken, and the result will be an empty array.

Here’s the code to implement the above logic:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

from collections import deque

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # Step 1: Create the graph and calculate in-degrees
        graph = [[] for _ in range(numCourses)]
        in_degree = [0] * numCourses

        for course, prereq in prerequisites:
            graph[prereq].append(course)
            in_degree[course] += 1

        # Step 2: Find starting points
        queue = deque([course for course in range(numCourses) if in_degree[course] == 0])
        result = []

        # Step 3: Topological Sort
        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)

        # Step 4: Check for cycles
        if len(result) != numCourses:
            return []

        return result

Explanation of the code:

• The graph is represented using an adjacency list, and the in-degree of each node is stored in an array.
• A queue is used to process the nodes in topological order.
• If the result does not contain all the courses, it means there’s a cycle, and an empty array is returned.

This code has a time complexity of O(N + E), where N is the number of courses, and E is the number of prerequisites, and a space complexity of O(N).