## Course Schedule II

###### DESCRIPTION (credit Leetcode.com)

You have to take a total of numCourses courses, which are labeled from 0 to numCourses - 1. You are given a list of prerequisites pairs, where prerequisites[i] = [a, b] indicates that you must complete course b before course a.

Given the total number of courses and a list of prerequisite pairs, write a function to return the ordering of courses you should take to finish all courses.

If there are multiple valid orderings, return any valid ordering. If it is impossible to finish all courses, return an empty array.

###### EXAMPLES

**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 couple of ways to complete all courses, one possible order is [0, 1, 2, 3] and another is [0, 2, 1, 3].

**Example 2:**

Input:

`numCourses = 2 prerequisites = [[1, 0], [0, 1]]`

Output: []

Explanation: It is impossible to finish all courses, as you must finish course 0 before course 1 and course 1 before course 0.

Run your code to see results here

## Explanation

We can solve this problem using the same approach as the Course Schedule problem. The only difference is that we need to return the order in which the courses should be taken.

In our solution, we first build a graph representing the prerequisites of each course. We then perform a topological sort on the graph to find the order in which the courses should be taken.

Now, we initialize an empty list called result to store the order of the courses. Each time we dequeue a course from the queue, we add it to the result list to keep track of the ordering of the courses.

Finally, when the queue is empty, we check if the result list has the same length as the number of courses. If it does, we return the result list. Otherwise, we return an empty list, as there is no valid ordering of the courses.

### Solution

from collections import defaultdict, dequeclass Solution:def findOrder(self, numCourses, prerequisites):graph = defaultdict(list)in_degree = [0] * numCoursesfor dest, src in prerequisites:graph[src].append(dest)in_degree[dest] += 1queue = deque([i for i in range(numCourses) if in_degree[i] == 0])order = []while queue:course = queue.popleft()order.append(course)for neighbor in graph[course]:in_degree[neighbor] -= 1if in_degree[neighbor] == 0:queue.append(neighbor)return order if len(order) == numCourses else []

### Complexity Analysis

The time complexity of this solution is O(V + E), where V is the number of courses and E is the number of prerequisites. This is because we perform a topological sort on the graph, which takes O(V + E) time.

The space complexity of this solution is O(V + E), where V is the number of courses and E is the number of prerequisites. This is because we store the graph and the in-degree of each course, which takes O(V + E) space.

Loading comments...