There are a total of `n`

courses you have to take labelled from `0`

to `n - 1`

.

Some courses may have `prerequisites`

, for example, if `prerequisites[i] = [ai, bi]`

this means you must take the course `bi`

before the course `ai`

.

Given the total number of courses `numCourses`

and a list of the `prerequisite`

pairs, 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]

**Constraints:**

`1 <= numCourses <= 2000`

`0 <= prerequisites.length <= numCourses * (numCourses - 1)`

`prerequisites[i].length == 2`

`0 <= ai, bi < numCourses`

`ai != bi`

- All the pairs
`[ai, bi]`

are**distinct**.

The description was taken from __https://leetcode.com/problems/course-schedule-ii/____.__

`#O(N+E) Time, O(N+E) Space`

**class** **Solution**:

` `**def** **findOrder**(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:

` seen, course_order, prereq_map = {}, {}, {}`

` `

` `**for** course **in** range(**0**, numCourses):

` prereq_map[course] = []`

` seen[course] = False`

` `

` `**for** course, prereq **in** prerequisites:

` prereq_map[course].append(prereq)`

` `

` `**def** **dfs**(course:int) -> bool:

` `**if** seen[course]:

` `**return** False

` `**if** course **in** course_order:

` `**return** True

` seen[course] = True`

` `**for** prereq **in** prereq_map[course]:

` `**if** **not** dfs(prereq):

` `**return** False

` seen[course] = False`

` prereq_map[course] = []`

` course_order[course] = True`

` `**return** True

` `

` `**for** course **in** range(**0**, numCourses):

` `**if** **not** dfs(course):

` `**return** []

` `**return** course_order.keys()

To figure out if we can complete the prerequisites for each course, we will need to get the relationships between each course and each prerequisite course that needs to be taken grouped together.

Without physically creating a graph by instantiating nodes using the input matrix, we can use an adjacency list to map each prerequisite to each course.

We can then solve this problem by performing a Depth-First Search on the number of courses that are input, go through their prerequisites and check off the ones we are able to take. If there are no cycles, meaning there aren't two classes that are prerequisites of each other then we should be able to take each course.

The only difference between this version of the question and the previous one is we will keep a course order HashMap that we will add each course to **after **the DFS of their prerequisite courses ends. By doing this, we will be able to first get the courses that are leaves at the bottom of the recursive tree, which would be the courses that have no prerequisites, then, get the courses that the leaves were prerequisites for, and so on.

This is the same idea as a postorder traversal on a binary tree.

Let's start up by creating our adjacency list,

, our **prereq_map**

hashmap that we will add each course to at the end of their DFS, and our **course_order **

dictionary to track cycles.**seen**

` seen, course_order, prereq_map = {}, {}, {}`

We will then go through the number of courses we have to initialize an empty prerequisite array within our adjacency list, and also add them to our seen dictionary with the initial value of false since we haven't seen them yet.

` `**for** course **in** range(**0**, numCourses):

` prereq_map[course] = []`

` seen[course] = False`

Next, we will go through each course and prerequisite given from the input prerequisites list and append each prerequisite to each course within our adjacency list.

` `**for** course, prereq **in** prerequisites:

` prereq_map[course].append(prereq)`

Now we will build our recursive,

function.**dfs **

It will take as arguments, a course integer and it will return a boolean value for which the prerequisites can be satisfied for the course without cycles.

` `

**def** **dfs**(course:int) -> bool:

Being a recursive function, we need to ensure the base cases aren't met before performing a DFS on the given course.

If the course has been seen in the current recursive tree, then that means the course this given prerequisite is for requires the initial course to also be taken as a prerequisite. Unless we try to bribe the dean of our college, we aren't going to be able to take the given courses so we will return false.

` `**if** seen[course]:

` `**return** False

Also, if the course is already in the

dictionary, we already said to take this course so we don't need to do any more work here.**course_order**

` `**if** course **in** course_order:

` `**return** True

If neither of these base cases is met, we will perform our DFS.

We'll breadcrumb our path by adding our current course to the seen dictionary.

` seen[course] = True`

Then, for each prerequisite mapped to the course within the adjacency list, we will see if their prerequisites can be satisfied. If at least one of them cannot be, then we should break from the loop early and return false because we would be wasting time investigating the remaining prerequisites.

` `**for** prereq **in** prereq_map[course]:

` `**if** **not** dfs(prereq):

` `**return** False

If the prerequisites for the given function call's course can be satisfied, then we will remove our breadcrumb, wipe our prerequisite array clean, add the course to the

dictionary, and let our recursive parent call know that the DFS is good from here.**course_order**

` seen[course] = False`

` prereq_map[course] = []`

` course_order[course] = True`

` `**return** True

Now, all there is left to do is make the initial calls.

We will iterate through each course number and run a DFS on it. The reason why we can't just run a DFS on one course and assume it will recursively run on every other course is that some courses may not have prerequisites nor are they prerequisites to others. In that case, it would be disconnected from the graph and wouldn't be searched.

If all of the courses return true from each path of their DFS, all courses can be taken, and we will return the

keys which will keep the order of when the courses were added from the DFS.**course_order **

` `**for** course **in** range(**0**, numCourses):

` `**if** **not** dfs(course):

` `**return** []

` `**return** course_order.keys()