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 {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> adj(numCourses);
        vector<int> color(numCourses, 0); // 0: unvisited, 1: visiting, 2: visited
        vector<int> order;
        bool valid = true;
        for (auto& p : prerequisites) {
            adj[p[1]].emplace_back(p[0]);
        }
        for (int i = 0; i < numCourses; i++) {
            if (color[i] == 0) dfs(i, adj, color, order, valid);
        }
        if (!valid) return {};
        reverse(order.begin(), order.end());
        return order;
    }

private:
    void dfs(int u, vector<vector<int>>& adj, vector<int>& color, vector<int>& order, bool& valid) {
        color[u] = 1;
        for (int v : adj[u]) {
            if (color[v] == 0) {
                dfs(v, adj, color, order, valid);
                if (!valid) return;
            } else if (color[v] == 1) {
                valid = false;
                return;
            }
        }
        color[u] = 2;
        order.emplace_back(u);
    }
};

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