mediumGraphsPattern: Topological Sort
Course Schedule Order Solution
Problem Statement
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`. Return a valid order of courses you can take to finish all courses. If it is impossible to finish all courses, return an empty array. Note that there may be multiple valid orderings, return any one of them.
Examples
Example 1:
Input:numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output:[0,1,2,3]
Explanation: There are a total of 4 courses to take. To take course 1 you should have finished course 0, and to take course 2 you should also have finished course 0. To take course 3 you should have finished both course 1 and course 2. A possible ordering is [0, 1, 2, 3] or [0, 2, 1, 3].
Example 2:
Input:numCourses = 2, prerequisites = [[1,0],[0,1]]
Output:[]
Explanation: There are a total of 2 courses. To take course 1 you should have finished course 0, and to take course 0 you should have finished course 1. This creates a cycle, so it is impossible to finish all courses.
Example 3:
Input:numCourses = 1, prerequisites = []
Output:[0]
Explanation: There is only one course and no prerequisites. You can take course 0.
Constraints
- 1 <= numCourses <= 2000
- 0 <= prerequisites.length <= 5000
- prerequisites[i].length == 2
- 0 <= ai, bi < numCourses
- ai != bi
- All pairs [ai, bi] are unique.
Time: O(V + E) Space: O(V + E)
Utilize Kahn's algorithm (BFS-based topological sort) or a DFS-based topological sort. Build an adjacency list representation of the graph and calculate in-degrees for each node. Add nodes with an in-degree of 0 to a queue. Process nodes from the queue, decrementing the in-degree of their neighbors. If a neighbor's in-degree becomes 0, add it to the queue. If the total number of courses processed equals `numCourses`, a valid order is found; otherwise, a cycle exists.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
from collections import defaultdict, deque
def find_order(num_courses, prerequisites):
adj = defaultdict(list)
in_degree = [0] * num_courses
for course, prereq in prerequisites:
adj[prereq].append(course)
in_degree[course] += 1
queue = deque()
for i in range(num_courses):
if in_degree[i] == 0:
queue.append(i)
result = []
while queue:
current_course = queue.popleft()
result.append(current_course)
for neighbor in adj[current_course]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return result if len(result) == num_courses else []