Log inSign up
mediumLeetCodeNot Started

Course Schedule II

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.

Graph
Solve on LeetCode
Lesson

Problem Statement

### 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] = [a_i, b_i] indicates that you must take course b_i first if you want to take course a_i.

- 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.

---

### Examples

Example 1: ``text 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: ``text Input: numCourses = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]] Output: [0, 2, 1, 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 course 0. So one correct course order is [0, 1, 2, 3]. Another correct ordering is [0, 2, 1, 3].

Example 3: ``text Input: numCourses = 1, prerequisites = [] Output: [0]

Example 4 (Cycle): ``text Input: numCourses = 2, prerequisites = [[1, 0], [0, 1]] Output: [] Explanation: There is a circular dependency between 0 and 1. No valid ordering exists, so return [].

---

### Constraints - 1 <= numCourses <= 2000 - 0 <= prerequisites.length <= numCourses * (numCourses - 1) - prerequisites[i].length == 2 - 0 <= a_i, b_i < numCourses - a_i != b_i - All the pairs [a_i, b_i] are distinct.

Constraints:

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= numCourses * (numCourses - 1)
  • prerequisites[i].length == 2
  • 0 <= a_i, b_i < numCourses
  • a_i != b_i
  • All the pairs [a_i, b_i] are distinct

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Produce a complete topological ordering of a directed graph.
  • Handle cycle detection gracefully by returning an empty array.
  • Compare Kahn's in-degree queue approach with DFS post-order reversal.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Find an execution order or schedule satisfying dependency constraints
  • Directed graph with potential cycles requiring empty output if invalid
  • Linear topological ordering of vertices in a DAG

Algorithmic Decision Tree:

  • 1. Build adjacency list b -> a and count in-degrees inDegree[a]++.
  • 2. Enqueue all vertices with inDegree[u] == 0.
  • 3. While queue has elements, pop u, append u to order, decrement inDegree[v]-- for neighbors. Enqueue when in-degree hits 0.
  • 4. Return order.length == numCourses ? order : [].

Connected Patterns:

Course ScheduleAlien DictionaryTopological Sort

1. Exhaustive Permutation Search

Intuition

Generate permutations of [0, 1, ..., numCourses - 1] and verify if all prerequisite dependencies are respected.

Algorithm

  1. Generate all permutations of numbers 0 to numCourses - 1.
  2. For each permutation, record the position index of each course.
  3. Check every prerequisite [a, b]: if pos[b] > pos[a], invalid permutation.
  4. If a permutation satisfies all prerequisites, return it.
  5. If all permutations are tested without success, return [].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4#include <algorithm>
5
6class Solution {
7 bool isValid(const std::vector<int>& order, const std::vector<std::vector<int>>& prerequisites, int n) {
8 std::vector<int> pos(n);
9 for (int i = 0; i < n; ++i) pos[order[i]] = i;
10 for (const auto& p : prerequisites) {
11 if (pos[p[1]] > pos[p[0]]) return false;
12 }
13 return true;
14 }
15public:
16 std::vector<int> findOrder(int numCourses, std::vector<std::vector<int>>& prerequisites) {
17 std::vector<int> order(numCourses);
18 std::iota(order.begin(), order.end(), 0);
19
20 do {
21 if (isValid(order, prerequisites, numCourses)) return order;
22 } while (std::next_permutation(order.begin(), order.end()));
23
24 return {};
25 }
26};
27
28int main() {
29 Solution sol;
30 std::vector<std::vector<int>> p = {{1, 0}};
31 auto res = sol.findOrder(2, p);
32 std::cout << "Order: [" << res[0] << ", " << res[1] << "] (Expected: [0, 1])\n";
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N! * E)
  • Space complexity: O(N)

2. DFS 3-Coloring with Post-Order Reversal

Intuition

Depth-first search with 3 visitation colors (white=0, gray=1, black=2). Add nodes to order on recursion exit, then reverse the result.

Algorithm

  1. Build directed adjacency list b -> a.
  2. Initialize state array of size numCourses with 0 (unvisited).
  3. Maintain a postOrder list.
  4. Define dfs(u):
  5. If state[u] == 1, return false (cycle detected).
  6. If state[u] == 2, return true (already processed).
  7. state[u] = 1.
  8. For each neighbor v in adj[u]:
  9. if (!dfs(v)) return false.
  10. state[u] = 2.
  11. postOrder.push(u).
  12. Return true.
  13. For each vertex i from 0 to numCourses - 1:
  14. If state[i] == 0 and !dfs(i), return [].
  15. Reverse postOrder and return it.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5class Solution {
6 bool dfs(int u, const std::vector<std::vector<int>>& adj, std::vector<int>& state, std::vector<int>& postOrder) {
7 state[u] = 1; // 1 = visiting
8
9 for (int v : adj[u]) {
10 if (state[v] == 1) return false; // Cycle detected
11 if (state[v] == 0) {
12 if (!dfs(v, adj, state, postOrder)) return false;
13 }
14 }
15
16 state[u] = 2; // 2 = visited
17 postOrder.push_back(u);
18 return true;
19 }
20public:
21 std::vector<int> findOrder(int numCourses, std::vector<std::vector<int>>& prerequisites) {
22 std::vector<std::vector<int>> adj(numCourses);
23 for (const auto& p : prerequisites) {
24 adj[p[1]].push_back(p[0]); // b -> a
25 }
26
27 std::vector<int> state(numCourses, 0);
28 std::vector<int> postOrder;
29
30 for (int i = 0; i < numCourses; ++i) {
31 if (state[i] == 0) {
32 if (!dfs(i, adj, state, postOrder)) return {};
33 }
34 }
35
36 std::reverse(postOrder.begin(), postOrder.end());
37 return postOrder;
38 }
39};
40
41int main() {
42 Solution sol;
43 std::vector<std::vector<int>> p = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};
44 auto order = sol.findOrder(4, p);
45 std::cout << "DFS Topological Order: [";
46 for (size_t i = 0; i < order.size(); ++i) std::cout << order[i] << (i + 1 < order.size() ? ", " : "");
47 std::cout << "]\n";
48 return 0;
49}

Time & Space Complexity

  • Time complexity: O(V + E)
  • Space complexity: O(V + E)

3. Kahn's Algorithm (BFS In-Degree Topological Sort - Industry Standard)

Intuition

Compute in-degrees for all courses. Enqueue courses with 0 in-degree. Record each dequeued course into the result array and decrement neighbor in-degrees.

Algorithm

  1. Initialize inDegree array of size numCourses with 0.
  2. Build directed adjacency list: for each [a, b], add adj[b].push(a) and inDegree[a]++.
  3. Initialize order array.
  4. Enqueue all courses i where inDegree[i] == 0.
  5. While queue is not empty:
  6. Pop course u from queue.
  7. Append u to order.
  8. For each dependent course v in adj[u]:
  9. inDegree[v]--.
  10. If inDegree[v] == 0, push v to queue.
  11. If order.length == numCourses, return order; else return [].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5class Solution {
6public:
7 std::vector<int> findOrder(int numCourses, std::vector<std::vector<int>>& prerequisites) {
8 std::vector<std::vector<int>> adj(numCourses);
9 std::vector<int> inDegree(numCourses, 0);
10
11 for (const auto& p : prerequisites) {
12 adj[p[1]].push_back(p[0]); // b -> a
13 inDegree[p[0]]++;
14 }
15
16 std::queue<int> q;
17 for (int i = 0; i < numCourses; ++i) {
18 if (inDegree[i] == 0) q.push(i);
19 }
20
21 std::vector<int> order;
22 order.reserve(numCourses);
23
24 while (!q.empty()) {
25 int u = q.front();
26 q.pop();
27 order.push_back(u);
28
29 for (int v : adj[u]) {
30 inDegree[v]--;
31 if (inDegree[v] == 0) {
32 q.push(v);
33 }
34 }
35 }
36
37 return order.size() == numCourses ? order : std::vector<int>{};
38 }
39};
40
41int main() {
42 Solution sol;
43 std::vector<std::vector<int>> p = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};
44 auto order = sol.findOrder(4, p);
45 std::cout << "Kahn Topological Order: [";
46 for (size_t i = 0; i < order.size(); ++i) std::cout << order[i] << (i + 1 < order.size() ? ", " : "");
47 std::cout << "] (Expected: [0, 1, 2, 3] or [0, 2, 1, 3])\n";
48 return 0;
49}

Time & Space Complexity

  • Time complexity: O(V + E)
  • Space complexity: O(V + E)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Exhaustive Permutation SearchO(N! * E)O(N)Generates all N! permutations and validates prerequisite ordering.N! permutations
2.DFS 3-Coloring with Post-Order ReversalO(V + E)O(V + E)Appends vertices on recursion return (post-order) and reverses the list.Call stack depth
3.Kahn's Algorithm (BFS In-Degree)OptimalO(V + E)O(V + E)Iteratively pops 0 in-degree nodes into the result array and decrements neighbor in-degrees.Queue pops

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Reversing edge direction (e.g. a -> b instead of b -> a).

Pitfall 2:

Returning partial results instead of empty array [] when a cycle is detected.

Pitfall 3:

Forgetting to check if order.length == numCourses before returning.

Crucial Edge Cases to Validate:

  • No prerequisites (prerequisites is empty) — All courses have in-degree 0; any permutation (e.g. [0, 1, ..., numCourses - 1]) is valid.
  • Single course with no prerequisites — Returns [0].
  • Circular dependency (cycle in graph) — Detected when order.length < numCourses -> returns [].
  • Disconnected components — Zero in-degree vertices from all components enter queue; all courses are safely ordered.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the progression: 'Course Schedule I is cycle detection (is it a DAG?), whereas Course Schedule II asks for the topological ordering itself.'
  2. Mention Kahn's algorithm: Kahns BFS is optimal here because appending popped in-degree 0 nodes constructs the order in-place without needing any reversal.'
  3. Emphasize the failure check: 'If the resulting order array size is less than numCourses, a cycle exists, so return an empty array [] immediately.'

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does Kahn's algorithm naturally produce the topological order directly without needing reversal?

2.Can a directed graph have more than one valid topological sort?

3.What should be returned if prerequisites = [[1, 0], [0, 1]]?

Back to DSA Sheet