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.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

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.

Additional information

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• ai != bi
• All the pairs [ai, bi] are distinct.

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,1,2,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]

Recursive Depth-First Search (Topological Sort)

Intuition

To find the correct order to take the courses, we need to perform a Topological Sort on the directed graph.

We can achieve this using Depth-First Search (DFS). The idea is to go as deep as possible down a prerequisite chain. Once we hit a course that unlocks nothing else (or all its unlocked courses are already processed), we know it can be safely added to our output list. By adding courses only after all of their subsequent dependent courses have been processed (post-order traversal), we build the schedule backwards. Reversing this list at the very end gives us the correct chronological order!

To prevent infinite loops and detect impossible circular dependencies (cycles), we maintain two sets:

1. cycle: Tracks nodes currently in our active DFS path. If we hit a node already in this set, a cycle exists.
2. visited: Tracks nodes we have completely finished processing. This prevents us from doing redundant work.

Algorithm

1. Build an adjacency list adj mapping each prerequisite (pre) to the courses it unlocks (crs).
2. Initialize an empty list res for the final order, and two sets visited and cycle.
3. Define a recursive helper function dfs(crs):

• If crs is in cycle, we found a circular dependency! Return False.
• If crs is in visited, we already processed it safely. Return True.
• Add crs to cycle to mark it as currently being explored.
• Loop through all neighbors in adj[crs]. If any recursive call to dfs(neighbor) returns False, return False.
• Remove crs from cycle and add it to visited.
• Append crs to res. (Because we add it after its descendants, the list is built in reverse).
• Return True.

4. Loop i from 0 to numCourses - 1. If dfs(i) returns False, return [].
5. After the loop finishes, reverse the res list and return it.

def find_order(num_courses: int, prerequisites: list[list[int]]) -> list[int]:
    # Map each prerequisite to the courses it unlocks
    adj = {i: [] for i in range(num_courses)}
    for crs, pre in prerequisites:
        adj[pre].append(crs)
        
    res = []
    visited = set()
    cycle = set()
    
    def dfs(crs):
        if crs in cycle:
            return False
        if crs in visited:
            return True
            
        cycle.add(crs)
        
        # Traverse all courses that require the current course
        for neighbor in adj[crs]:
            if not dfs(neighbor):
                return False
                
        # Backtrack and mark as completely processed
        cycle.remove(crs)
        visited.add(crs)
        res.append(crs)
        return True
        
    for i in range(num_courses):
        if not dfs(i):
            return []
            
    # The list is built in reverse chronological order, so reverse it
    res.reverse()
    return res

Time & Space Complexity

• Time complexity: O(V + E)

• Reason: We visit every Vertex (course) and every Edge (prerequisite connection) exactly once. Building the adjacency list takes O(E) time.

• Space complexity: O(V + E)

• Reason: The adjacency list takes O(V + E) space. The res list, visited set, cycle set, and the recursion stack all take up to O(V) space.

Iterative BFS (Kahn's Algorithm) - Optimal

Intuition

We can also generate the topological sort using an iterative Breadth-First Search (BFS) known as Kahn's Algorithm. This avoids deep recursion stacks and builds the schedule chronologically from start to finish without needing to reverse anything.

We calculate the "in-degree" (the number of prerequisite locks) for every course. Any course with an in-degree of 0 is completely unlocked and can be taken immediately. We put these 0-in-degree courses into a Queue.

As we pop a course from the Queue, we append it directly to our final res array. Then, we simulate "taking" the course by looking at all the subsequent courses that depend on it, and subtracting 1 from their in-degree locks. If a dependent course's in-degree drops to 0, it is now unlocked, and we push it into the Queue!

Algorithm

1. Initialize an adjacency list adj and an indegree array/dictionary for all courses set to 0.
2. Iterate through prerequisites. For [crs, pre], add crs to adj[pre] and increment indegree[crs] by 1.
3. Initialize a deque (queue).
4. Iterate through all courses. If indegree[i] == 0, append i to the queue.
5. Initialize an empty list res.
6. While the queue is not empty:

• Pop the front course curr.
• Append curr to res.
• Iterate through the neighbors in adj[curr].
• Decrement the indegree[neighbor] by 1.
• If indegree[neighbor] reaches 0, append it to the queue.

7. If len(res) == numCourses, we successfully scheduled everything. Return res. Otherwise, a cycle blocked us, so return [].

def find_order(num_courses: int, prerequisites: list[list[int]]) -> list[int]:
    adj = {i: [] for i in range(num_courses)}
    indegree = {i: 0 for i in range(num_courses)}
    
    # Build adjacency list and in-degree counts
    for crs, pre in prerequisites:
        adj[pre].append(crs)
        indegree[crs] += 1
        
    q = deque()
    
    # Queue all courses that have no prerequisites
    for i in range(num_courses):
        if indegree[i] == 0:
            q.append(i)
            
    res = []
    
    # Process the courses
    while q:
        curr = q.popleft()
        res.append(curr)
        
        # Unlock dependent courses
        for neighbor in adj[curr]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                q.append(neighbor)
                
    # If we couldn't take all courses, there was a cycle
    if len(res) == num_courses:
        return res
    return []

Time & Space Complexity

• Time complexity: O(V + E)

• Reason: Initializing the adjacency list and in-degrees takes O(E). Finding the initial 0 in-degree nodes takes O(V). Processing the queue visits each node and its edges exactly once, taking O(V + E).

• Space complexity: O(V + E)

• Reason: The adjacency list adj holds all Vertices and Edges. The indegree map, the queue, and the res list hold at most V elements.