Log inSign up
mediumLeetCodeNot Started

Course Schedule

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 true if you can finish all courses. Otherwise, return false.

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 true if you can finish all courses. Otherwise, return false.

---

### Examples

Example 1: ``text Input: numCourses = 2, prerequisites = [[1, 0]] Output: true Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible: take course 0 then course 1.

Example 2: ``text Input: numCourses = 2, prerequisites = [[1, 0], [0, 1]] Output: false Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible due to circular dependency.

Example 3: ``text Input: numCourses = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]] Output: true Explanation: A valid order is: 0 -> 1 -> 2 -> 3. All courses can be finished.

---

### Constraints - 1 <= numCourses <= 2000 - 0 <= prerequisites.length <= 5000 - prerequisites[i].length == 2 - 0 <= a_i, b_i < numCourses - All the pairs prerequisites[i] are unique.

Constraints:

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= a_i, b_i < numCourses
  • All the pairs prerequisites[i] are unique

What You'll Learn

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

  • Model prerequisite dependencies as directed graphs.
  • Understand cycle detection equivalence to topological sort feasibility.
  • Implement Kahn's in-degree BFS algorithm with O(V + E) efficiency.

Pattern Recognition Trigger

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

Signals to Look For:

  • Ordering tasks with dependencies
  • Prerequisites represented as directed pairs
  • Question asks whether a valid schedule or ordering is possible

Algorithmic Decision Tree:

  • 1. Build adjacency list b -> a and track inDegree[a]++.
  • 2. Enqueue all nodes with inDegree[u] == 0.
  • 3. Pop from queue, increment count, decrement neighbor in-degrees. Enqueue neighbors whose in-degree becomes 0.
  • 4. Return count == numCourses.

Connected Patterns:

Course Schedule IIAlien DictionaryTopological Sort

1. Naive Cycle Search from Every Vertex via DFS

Intuition

Start a separate DFS traversal from every single vertex with a local path visited set to check if any path loops back to the start.

Algorithm

  1. Build directed adjacency list where b -> a.
  2. For each vertex i from 0 to numCourses - 1:
  3. Maintain a visited set for the current path search.
  4. Perform DFS from i.
  5. If DFS encounters a node currently in visited, a cycle exists -> return false.
  6. If no cycle is found from any starting vertex, return true.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5 bool hasCycle(int u, const std::vector<std::vector<int>>& adj, std::vector<bool>& onPath) {
6 onPath[u] = true;
7 for (int v : adj[u]) {
8 if (onPath[v]) return true; // Cycle detected
9 if (hasCycle(v, adj, onPath)) return true;
10 }
11 onPath[u] = false;
12 return false;
13 }
14public:
15 bool canFinish(int numCourses, std::vector<std::vector<int>>& prerequisites) {
16 std::vector<std::vector<int>> adj(numCourses);
17 for (const auto& p : prerequisites) {
18 adj[p[1]].push_back(p[0]); // p[1] -> p[0]
19 }
20
21 for (int i = 0; i < numCourses; ++i) {
22 std::vector<bool> onPath(numCourses, false);
23 if (hasCycle(i, adj, onPath)) return false;
24 }
25 return true;
26 }
27};
28
29int main() {
30 Solution sol;
31 std::vector<std::vector<int>> p1 = {{1, 0}};
32 std::cout << "Can finish p1: " << (sol.canFinish(2, p1) ? "true" : "false") << " (Expected: true)\n";
33 std::vector<std::vector<int>> p2 = {{1, 0}, {0, 1}};
34 std::cout << "Can finish p2: " << (sol.canFinish(2, p2) ? "true" : "false") << " (Expected: false)\n";
35 return 0;
36}

Time & Space Complexity

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

2. DFS 3-Coloring Cycle Detection

Intuition

Classify nodes into 3 states: 0 = unvisited (white), 1 = visiting on recursion stack (gray), 2 = fully visited (black). Cycle exists if a gray node is reached.

Algorithm

  1. Build directed adjacency list.
  2. Initialize state array of size numCourses with 0.
  3. Define dfs(u):
  4. If state[u] == 1, return true (cycle detected).
  5. If state[u] == 2, return false (already safe).
  6. state[u] = 1.
  7. For each neighbor v in adj[u]:
  8. If dfs(v) returns true, return true.
  9. state[u] = 2 (mark processed).
  10. Return false.
  11. For each vertex i from 0 to numCourses - 1:
  12. If state[i] == 0 and dfs(i) is true, return false.
  13. Return true.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5 bool hasCycle(int u, const std::vector<std::vector<int>>& adj, std::vector<int>& state) {
6 state[u] = 1; // 1 = visiting (in stack)
7
8 for (int v : adj[u]) {
9 if (state[v] == 1) return true; // Cycle detected
10 if (state[v] == 0) {
11 if (hasCycle(v, adj, state)) return true;
12 }
13 }
14
15 state[u] = 2; // 2 = visited & safe
16 return false;
17 }
18public:
19 bool canFinish(int numCourses, std::vector<std::vector<int>>& prerequisites) {
20 std::vector<std::vector<int>> adj(numCourses);
21 for (const auto& p : prerequisites) {
22 adj[p[1]].push_back(p[0]);
23 }
24
25 std::vector<int> state(numCourses, 0); // 0 = unvisited, 1 = visiting, 2 = visited
26 for (int i = 0; i < numCourses; ++i) {
27 if (state[i] == 0) {
28 if (hasCycle(i, adj, state)) return false;
29 }
30 }
31 return true;
32 }
33};
34
35int main() {
36 Solution sol;
37 std::vector<std::vector<int>> p1 = {{1, 0}};
38 std::cout << "3-Color DFS p1: " << (sol.canFinish(2, p1) ? "true" : "false") << " (Expected: true)\n";
39 std::vector<std::vector<int>> p2 = {{1, 0}, {0, 1}};
40 std::cout << "3-Color DFS p2: " << (sol.canFinish(2, p2) ? "true" : "false") << " (Expected: false)\n";
41 return 0;
42}

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. Seed queue with courses having 0 in-degree. Iteratively remove courses 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. Enqueue all courses i where inDegree[i] == 0.
  4. Initialize processedCount = 0.
  5. While queue is not empty:
  6. Pop course u from queue, increment processedCount.
  7. For each dependent course v in adj[u]:
  8. inDegree[v]--.
  9. If inDegree[v] == 0, push v to queue.
  10. Return processedCount == numCourses.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5class Solution {
6public:
7 bool canFinish(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 // Build graph: b -> a
12 for (const auto& p : prerequisites) {
13 adj[p[1]].push_back(p[0]);
14 inDegree[p[0]]++;
15 }
16
17 // Seed queue with nodes of in-degree 0
18 std::queue<int> q;
19 for (int i = 0; i < numCourses; ++i) {
20 if (inDegree[i] == 0) q.push(i);
21 }
22
23 int completed = 0;
24 while (!q.empty()) {
25 int u = q.front();
26 q.pop();
27 completed++;
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 completed == numCourses;
38 }
39};
40
41int main() {
42 Solution sol;
43 std::vector<std::vector<int>> p1 = {{1, 0}};
44 std::cout << "Kahn BFS p1: " << (sol.canFinish(2, p1) ? "true" : "false") << " (Expected: true)\n";
45 std::vector<std::vector<int>> p2 = {{1, 0}, {0, 1}};
46 std::cout << "Kahn BFS p2: " << (sol.canFinish(2, p2) ? "true" : "false") << " (Expected: false)\n";
47 return 0;
48}

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.Naive Cycle Search from Every VertexO(V * (V + E))O(V + E)Starts a path-checking DFS from each node without memoizing visited states.Repeated full DFS passes
2.DFS 3-Coloring Cycle DetectionO(V + E)O(V + E)Uses 3 states (unvisited, visiting, visited) to identify back-edges.Call stack depth
3.Kahn's Algorithm (BFS In-Degree)OptimalO(V + E)O(V + E)Enqueues in-degree 0 nodes, decrements dependencies, counts finished courses.Queue pops

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Reversing the edge direction: building a -> b instead of b -> a.

Pitfall 2:

Using a simple boolean visited array with DFS, which fails to distinguish cross-edges from back-edges.

Pitfall 3:

Not initializing in-degrees for all numCourses courses, missing disconnected nodes.

Crucial Edge Cases to Validate:

  • No prerequisites (prerequisites is empty) — All courses have in-degree 0 and enter the queue immediately -> returns true.
  • Self-loop (e.g. [[0, 0]]) — inDegree[0] is 1 with no incoming edge from another node -> never enqueued -> returns false.
  • Direct cycle (e.g. [[0, 1], [1, 0]]) — Both nodes have in-degree 1; queue starts empty -> returns false.
  • Disconnected components (multiple independent subgraphs) — In-degree 0 nodes from all components enter queue; processedCount counts all components.

Interview Tips & Best Practices

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

  1. State the graph translation clearly: 'This is equivalent to detecting whether a directed graph contains a cycle (is a DAG).'
  2. Clarify edge direction out loud: 'Since b is a prerequisite for a, the dependency flows from b to a.'
  3. Highlight why Kahn's algorithm is preferred: Kahns BFS avoids recursion stack limits and generalizes directly to Course Schedule II by simply recording the popped sequence.'

Quick Comprehension Check

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

1.In the pair [a, b], which direction should the directed edge point in the graph?

2.Why does Kahn's algorithm successfully detect a cycle in a directed graph?

3.What is the time complexity of Kahn's Algorithm on a graph with V vertices and E edges?

Back to DSA Sheet