Course Schedule II
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 course0
you have to first take course1
.
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.
Solution
The problems asks us to find the ordering of courses to take. We know this involves the dependency of courses, so we will find the topological ordering of these courses.
We will build a graph with directed edges from a course
's prereq
to course
itself, then find the topological sorting of the graph.
Implementation
1def findOrder(numCourses: int, prerequisites: List[List[int]]) -> List[int]:
2 visited = [False for _ in range(numCourses)]
3 finished = []
4 graph = defaultdict(list)
5
6 for course, prereq in prerequisites:
7 graph[prereq].append(course)
8
9 def dfs(prereq):
10 for course in graph[prereq]:
11 if not visited[course]:
12 visited[course] = True
13 if not dfs(course): return False # unable to finish course
14 elif course not in finished: # cycle in graph
15 return False
16 finished.append(prereq)
17 return True
18
19 for i in range(numCourses): # visit all trees in graph
20 if not visited[i]:
21 visited[i] = True
22 if not dfs(i): return []
23
24 finished.reverse() # topological ordering = reverse finish time
25 return finished
Which algorithm is best for finding the shortest distance between two points in an unweighted graph?
Which data structure is used in a depth first search?
A heap is a ...?
What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.