View on NeetCode
View on LeetCode

Problem

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.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: There are 2 courses. 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 4 courses. One possible order is [0,2,1,3].
Another possible order is [0,1,2,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

Approach 1: DFS with Topological Sort

The key insight is to perform DFS and add courses to the result in post-order (after visiting all prerequisites), then reverse the result.

Implementation

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # Build adjacency list
        graph = [[] for _ in range(numCourses)]
        for course, prereq in prerequisites:
            graph[course].append(prereq)

        # 0 = unvisited, 1 = visiting, 2 = visited
        visit = [0] * numCourses
        order = []

        def dfs(course):
            if visit[course] == 1:  # Cycle detected
                return False
            if visit[course] == 2:  # Already processed
                return True

            visit[course] = 1

            # Visit all prerequisites
            for prereq in graph[course]:
                if not dfs(prereq):
                    return False

            visit[course] = 2
            order.append(course)
            return True

        # Process all courses
        for course in range(numCourses):
            if not dfs(course):
                return []

        return order

Approach 2: Kahn’s Algorithm (BFS Topological Sort)

from collections import deque

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # Build adjacency list and in-degree array
        graph = [[] for _ in range(numCourses)]
        in_degree = [0] * numCourses

        for course, prereq in prerequisites:
            graph[prereq].append(course)
            in_degree[course] += 1

        # Start with courses that have no prerequisites
        queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
        order = []

        while queue:
            course = queue.popleft()
            order.append(course)

            # Process courses that depend on this one
            for next_course in graph[course]:
                in_degree[next_course] -= 1
                if in_degree[next_course] == 0:
                    queue.append(next_course)

        # If we processed all courses, return the order
        return order if len(order) == numCourses else []

Complexity Analysis

Both Approaches:

• Time Complexity: O(V + E), where V is number of courses and E is number of prerequisites.
• Space Complexity: O(V + E) for the adjacency list and auxiliary data structures.

Key Insights

1. Topological Ordering: The problem asks for a topological sort of the course dependency graph.

2. DFS Post-Order: In DFS approach, we add courses to result after visiting all their prerequisites (post-order), giving us reverse topological order.

3. Kahn’s Natural Order: BFS (Kahn’s algorithm) naturally produces courses in the correct order by processing nodes with no remaining dependencies.

4. Cycle Detection: Both approaches detect cycles - DFS with visiting state, Kahn’s by checking if all courses were processed.

5. Multiple Valid Orders: Many valid orderings may exist. Both approaches return one valid ordering.

6. Empty Graph: When there are no prerequisites, any ordering works - Kahn’s naturally handles this by starting with all courses.