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.

  • 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:

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.

Example 2:

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.

Constraints

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

Thinking Process

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.

  • For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

  • 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

Solution 1: Topological Sort (Kahn’s Algorithm)

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        int[] indeg = new int[numCourses];
        for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
        for (int[] p : prerequisites) {
            graph.get(p[1]).add(p[0]);
            indeg[p[0]]++;
        }
        ArrayDeque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) q.offer(i);
        int seen = 0;
        while (!q.isEmpty()) {
            int u = q.poll();
            seen++;
            for (int v : graph.get(u)) {
                if (--indeg[v] == 0) q.offer(v);
            }
        }
        return seen == numCourses;
    }
}```

### Solution Explanation

**Approach:** BFS / DFS traversal (this problem)

**Key idea:** 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`.

**How the code works:**
- For example, the pair `[0, 1]`, indicates that to take course `0` you have to first take course `1`.
- 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 `true`:

There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

### **Solution 2: DFS Cycle Detection**

```java
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        int[] indeg = new int[numCourses];
        for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
        for (int[] p : prerequisites) {
            graph.get(p[1]).add(p[0]);
            indeg[p[0]]++;
        }
        ArrayDeque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) q.offer(i);
        int seen = 0;
        while (!q.isEmpty()) {
            int u = q.poll();
            seen++;
            for (int v : graph.get(u)) {
                if (--indeg[v] == 0) q.offer(v);
            }
        }
        return seen == numCourses;
    }
}```

### **Algorithm Explanation:**

#### **Topological Sort Approach:**
1. **Build graph**: Create adjacency list and calculate indegrees
2. **Initialize queue**: Add all courses with indegree 0 (no prerequisites)
3. **Process**: Remove course from queue, decrement indegrees of its neighbors
4. **Add to queue**: If neighbor's indegree becomes 0, add to queue
5. **Check completion**: If count equals numCourses, all courses can be completed

#### **DFS Cycle Detection Approach:**
1. **Three states**: 0=unvisited, 1=visiting, 2=visited
2. **DFS from each unvisited node**: Check for cycles
3. **Cycle detection**: If we encounter a "visiting" node during DFS, cycle exists
4. **State transitions**: unvisited → visiting → visited

### **Example Walkthrough:**

**For `numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]`:**

Graph: 0 → 1 → 3 ↘ 2 ↗

Topological Sort:

  1. Indegrees: [0,1,1,2]
  2. Start with course 0 (indegree=0)
  3. Remove 0: indegrees become [0,0,0,2]
  4. Add courses 1,2 to queue
  5. Remove 1: indegrees become [0,0,0,1]
  6. Remove 2: indegrees become [0,0,0,0]
  7. Add course 3 to queue
  8. Remove 3: count=4, return true

DFS Cycle Detection:

  1. Start DFS from course 0
  2. Visit 0: state[0]=1 (visiting)
  3. Visit 1: state[1]=1 (visiting)
  4. Visit 3: state[3]=1 (visiting)
  5. No more neighbors, state[3]=2 (visited)
  6. Back to 1: state[1]=2 (visited)
  7. Back to 0: state[0]=2 (visited)
  8. Continue with courses 2,3…
  9. No cycles found, return true ```

Time Complexity: O(V + E)

  • V: Number of courses (numCourses)
  • E: Number of prerequisites
  • Graph building: O(E)
  • Traversal: O(V + E)
  • Total: O(V + E)

Space Complexity: O(V + E)

  • Adjacency list: O(V + E)
  • Indegree array: O(V)
  • Queue/Stack: O(V)
  • State array: O(V)
  • Total: O(V + E)

    Key Points

  1. Graph problem: Courses and prerequisites form a directed graph
  2. Cycle detection: Cycle means impossible to complete all courses
  3. Two approaches: Topological sort and DFS both work
  4. Topological sort: More intuitive for this problem
  5. DFS: More general approach for cycle detection

Comparison: Topological Sort vs DFS

Aspect Topological Sort DFS Cycle Detection
Approach Indegree counting Three-state coloring
Intuition Process courses in order Detect cycles directly
Space Queue + Indegree array Recursion stack + State array
Code More straightforward More elegant
Performance Similar Similar

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.

Tags

Graph, Topological Sort, Cycle Detection, DFS, Medium

Key Takeaways

  • For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
  • Model entities as nodes and relationships as edges.
  • Pick traversal (BFS/DFS) or shortest-path (Dijkstra) based on weights.

References

Template Reference