You have numCourses courses labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] means you must take course bi before course ai. Return any valid ordering of courses to finish all of them, or an empty array if it is impossible.

Examples

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: To take course 1 you must take course 0 first. So [0,1] is valid.

Example 2:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3] (or [0,1,2,3], etc.)
Explanation: 0 has no prereq; 1 and 2 depend on 0; 3 depends on 1 and 2.

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 pairs are distinct

Thinking Process

  1. Prerequisite = edge: [a, b] means b → a in the graph; topological order has predecessors before successors.
  • Model entities as nodes and relationships as edges.
  • Pick traversal (BFS/DFS) or shortest-path (Dijkstra) based on weights.
  • Union-Find helps when connectivity updates are frequent.
Graph BFS layers S a b t BFS: expand by layers (queue)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
BFS / DFS traversal (this problem) O(V+E) O(V) Connectivity, flood fill
Dijkstra O((V+E)log V) O(V) Non-negative edge weights
Union-Find (DSU) O(α(n)) O(n) Dynamic connectivity
Topological sort O(V+E) O(V) DAG ordering, cycle detection

Solution

class Solution:
    def findOrder(self, numCourses, prerequisites):
        adj = [[] for _ in range(numCourses)]
        
        for a, b in prerequisites:
            adj[b].append(a)
        
        color = [0] * numCourses  # 0=unvisited, 1=visiting, 2=visited
        order = []
        valid = True
        
        def dfs(u):
            nonlocal valid
            
            color[u] = 1
            
            for v in adj[u]:
                if color[v] == 0:
                    dfs(v)
                    if not valid:
                        return
                elif color[v] == 1:
                    valid = False
                    return
            
            color[u] = 2
            order.append(u)
        
        for i in range(numCourses):
            if color[i] == 0:
                dfs(i)
                if not valid:
                    return []
        
        return order[::-1]

Solution Explanation

Approach: BFS / DFS traversal (this problem)

Key idea: 1. Prerequisite = edge: [a, b] means b → a in the graph; topological order has predecessors before successors.

How the code works:

  1. Prerequisite = edge: [a, b] means b → a in the graph; topological order has predecessors before successors.
    • Model entities as nodes and relationships as edges.
    • Pick traversal (BFS/DFS) or shortest-path (Dijkstra) based on weights.
    • Union-Find helps when connectivity updates are frequent.

Walkthrough — input numCourses = 2, prerequisites = [[1,0]], expected output [0,1]:

To take course 1 you must take course 0 first. So [0,1] is valid.

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

Comparison

Approach Idea Cycle check
DFS + coloring Finish order → reverse Back edge (color == 1)
Kahn (BFS) Indegree 0 → order order.size() != numCourses

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Key Takeaways

  1. Prerequisite = edge: [a, b] means b → a in the graph; topological order has predecessors before successors.
  2. DFS order: Finishing order is reverse topological; one reverse gives a valid schedule.
  3. Kahn: No need to reverse; order is built in topological order as we dequeue.

References

Template Reference