Approach

Course Schedule

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] = [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.

Approach

Key Insight

This is a Cycle Detection problem!

A course schedule is valid if and only if the prerequisite graph has no cycles.

Can be solved with:

DFS with colors (White → Gray → Black)
Topological Sort (Kahn's algorithm)
Union-Find (less common)

Solution 1: DFS Cycle Detection

Use three states: unvisited (0), visiting (1), visited (2).

Algorithm:

Build adjacency list from prerequisites
For each course:
- Start DFS
- Mark as visiting (1)
- Visit all neighbors
- If neighbor is visiting (1) → CYCLE!
- If neighbor is visited (2) → skip
- Mark as visited (2) when done
Return true if no cycles found

Solution 2: Topological Sort (Kahn's Algorithm)

BFS-based approach using in-degrees.

Algorithm:

Build adjacency list and in-degree array
Add all courses with in-degree 0 to queue
While queue not empty:
- Remove course from queue
- Decrement in-degree of neighbors
- If neighbor's in-degree becomes 0, add to queue
Return true if all courses processed

Solution 3: DFS with Visited Set

Alternative DFS using recursion stack tracking.

Algorithm:

Build adjacency list
Track globally visited and current path
DFS with backtracking
Cycle if node revisited in current path

Complexity Analysis

DFS Solution:

Time Complexity: O(V + E) - visit each node and edge once
Space Complexity: O(V + E) - adjacency list + recursion stack

Topological Sort:

Time Complexity: O(V + E) - process each node and edge once
Space Complexity: O(V + E) - adjacency list + queue

Where V = numCourses, E = prerequisites.length

Pattern Recognition

This problem demonstrates:

Cycle Detection in directed graphs
Graph coloring (White-Gray-Black)
Topological Sort fundamentals
DFS vs BFS trade-offs
Foundation for scheduling/dependency problems

Solution

java

1import java.util.*;
2
3class Solution {
4    // Solution 1: DFS Cycle Detection (Three Colors)
5    public boolean canFinish(int numCourses, int[][] prerequisites) {
6        // Build adjacency list
7        List<List<Integer>> graph = new ArrayList<>();
8        for (int i = 0; i < numCourses; i++) {
9            graph.add(new ArrayList<>());
10        }
11        for (int[] prereq : prerequisites) {
12            graph.get(prereq[1]).add(prereq[0]);
13        }
14
15        // States: 0 = unvisited, 1 = visiting, 2 = visited
16        int[] state = new int[numCourses];
17
18        // Check each course
19        for (int course = 0; course < numCourses; course++) {
20            if (hasCycle(course, graph, state)) {
21                return false;
22            }
23        }
24
25        return true;
26    }
27
28    private boolean hasCycle(int course, List<List<Integer>> graph, int[] state) {
29        if (state[course] == 1) {  // Currently visiting - CYCLE!
30            return true;
31        }
32        if (state[course] == 2) {  // Already visited
33            return false;
34        }
35
36        // Mark as visiting
37        state[course] = 1;
38
39        // Visit all neighbors
40        for (int neighbor : graph.get(course)) {
41            if (hasCycle(neighbor, graph, state)) {
42                return true;
43            }
44        }
45
46        // Mark as visited
47        state[course] = 2;
48        return false;
49    }
50
51    // Solution 2: Topological Sort (Kahn's Algorithm)
52    public boolean canFinishBFS(int numCourses, int[][] prerequisites) {
53        // Build adjacency list and in-degree array
54        List<List<Integer>> graph = new ArrayList<>();
55        int[] inDegree = new int[numCourses];
56
57        for (int i = 0; i < numCourses; i++) {
58            graph.add(new ArrayList<>());
59        }
60
61        for (int[] prereq : prerequisites) {
62            graph.get(prereq[1]).add(prereq[0]);
63            inDegree[prereq[0]]++;
64        }
65
66        // Start with courses that have no prerequisites
67        Queue<Integer> queue = new LinkedList<>();
68        for (int course = 0; course < numCourses; course++) {
69            if (inDegree[course] == 0) {
70                queue.offer(course);
71            }
72        }
73
74        int processed = 0;
75
76        // Process courses
77        while (!queue.isEmpty()) {
78            int course = queue.poll();
79            processed++;
80
81            // Reduce in-degree of neighbors
82            for (int neighbor : graph.get(course)) {
83                inDegree[neighbor]--;
84                if (inDegree[neighbor] == 0) {
85                    queue.offer(neighbor);
86                }
87            }
88        }
89
90        // All courses processed if no cycle
91        return processed == numCourses;
92    }
93
94    // Solution 3: DFS with Path Tracking
95    public boolean canFinishPath(int numCourses, int[][] prerequisites) {
96        // Build adjacency list
97        List<List<Integer>> graph = new ArrayList<>();
98        for (int i = 0; i < numCourses; i++) {
99            graph.add(new ArrayList<>());
100        }
101        for (int[] prereq : prerequisites) {
102            graph.get(prereq[1]).add(prereq[0]);
103        }
104
105        Set<Integer> visited = new HashSet<>();
106        Set<Integer> path = new HashSet<>();
107
108        // Check each course
109        for (int course = 0; course < numCourses; course++) {
110            if (!visited.contains(course)) {
111                if (!dfs(course, graph, visited, path)) {
112                    return false;
113                }
114            }
115        }
116
117        return true;
118    }
119
120    private boolean dfs(int course, List<List<Integer>> graph,
121                       Set<Integer> visited, Set<Integer> path) {
122        if (path.contains(course)) {  // Cycle detected!
123            return false;
124        }
125        if (visited.contains(course)) {  // Already checked
126            return true;
127        }
128
129        // Add to current path
130        path.add(course);
131
132        // Visit neighbors
133        for (int neighbor : graph.get(course)) {
134            if (!dfs(neighbor, graph, visited, path)) {
135                return false;
136            }
137        }
138
139        // Remove from path (backtrack)
140        path.remove(course);
141        visited.add(course);
142        return true;
143    }
144}
145