LeetEye LeetEye
Medium Graph Traversal ~5 min

Course Schedule II

graphs course-schedule-ii

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.

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.

Examples

Example 1
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3] or [0,1,2,3]
Example 2
Input: numCourses = 1, prerequisites = []
Output: [0]
Key Insight

Topological sort: order nodes so all edges go forward.

Topological sort: DFS post-order (reversed) or Kahn's (process 0 in-degree first). If can't include all nodes, cycle exists, return empty.

How to Approach This Problem

Pattern Recognition: When you see keywords like course schedule ii graphs, think Graph Traversal.

Step-by-Step Reasoning

1 A topological order of a DAG is:
Answer: Order where all prerequisites come before dependents
If A must come before B, A appears earlier in topological order.
2 DFS topological sort uses:
Answer: Post-order traversal (then reverse)
We add nodes to result AFTER processing all descendants. Reversing gives correct order.
3 Kahn's algorithm processes nodes in order of:
Answer: In-degree (starting with 0 in-degree)
Nodes with no prerequisites can be taken first. Remove them, update in-degrees, repeat.
4 If there's a cycle:
Answer: We can't produce any valid ordering
Cyclic dependencies have no valid ordering. Return empty.
5 For prerequisites [[1,0],[2,0]], valid orderings include:
Answer: Both [0,1,2] and [0,2,1]
0 must come first, but 1 and 2 can be in either order.

Solution

def findOrder(numCourses: int, prerequisites: List[List[int]]) -> List[int]:
    graph = {i: [] for i in range(numCourses)}
    for course, prereq in prerequisites:
        graph[course].append(prereq)
    
    result = []
    state = [0] * numCourses  # 0=unvisited, 1=visiting, 2=visited
    
    def dfs(course):
        if state[course] == 1:  # Cycle
            return False
        if state[course] == 2:  # Already added
            return True
        
        state[course] = 1
        
        for prereq in graph[course]:
            if not dfs(prereq):
                return False
        
        state[course] = 2
        result.append(course)  # Post-order
        return True
    
    for course in range(numCourses):
        if not dfs(course):
            return []
    
    return result  # Already in correct order (prereqs first)

Complexity Analysis

Time O(V + E)
Space O(V + E)

Master This Pattern

Build intuition with interactive MCQs. Practice Graph Traversal problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye