Difficulty: MediumGraphs

Course Schedule

Problem in Plain English

Given a course count and prerequisite pairs, decide whether every course can be finished. The answer is yes exactly when the prerequisite graph has no directed cycle.

Problem Statement

There are numCourses courses labeled 0 to numCourses - 1, plus an array prerequisites where prerequisites[i] = [a, b] means course b must be taken before course a.

Return true if all courses can be finished and false otherwise; a dependency cycle makes finishing impossible.

Constraints

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= a, b < numCourses
All prerequisite pairs are unique.

Examples

Example 1

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true

Take course 0 first, then course 1, so every course finishes.

Example 2

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false

Course 1 needs course 0 while course 0 needs course 1, a cycle nobody can start.

Example 3

Input: numCourses = 1, prerequisites = []
Output: true

The single course has no prerequisite, so it can be taken immediately. An empty edge list does not mean there are no courses.

Example 4

Input: numCourses = 4, prerequisites = [[1,0],[0,1],[3,2]]
Output: false

Courses 2 then 3 can finish, but 0 and 1 require each other. Finishing one disconnected component is insufficient: every course must finish.

Example 5

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: true

Finish 0, then 1 and 2 in either order, then 3. Course 3 becomes ready only after both of its prerequisites finish; a shared dependent is not a cycle.

Intuition

A prerequisite pair [1,0] is a directed edge from 0 to 1: course 0 unlocks course 1. Count how many prerequisites of each course are still unfinished. A zero count means the course is ready; finishing it removes one requirement from each dependent. Example 1 starts with counts [0,1], then taking 0 changes them to [0,0] so 1 can finish too. A cycle has no first course, so if ready courses run out with any course unfinished, the answer is false.

Approaches

Repeated Scan Kahn

Solution Details

Reveal Repeated Scan Kahn: intuition, complexity, and code

Intuition

A course with no remaining prerequisites can always go next, so repeatedly scanning every course for a zero-prerequisite pick builds a valid order or stalls at a cycle. Restarting the scan is the bottleneck: already taken prefixes are inspected again after each placement.

Step-by-Step Logic

Build adjacency from prerequisite b to dependent a for every pair [a,b], and increment need[a]. Initialize all taken flags to false; Example 1 produces graph=[[1],[]] and need=[0,1].
Repeat up to numCourses rounds. Start pick at -1 and scan labels from 0 upward for the first untaken course with need equal to zero. Example 1 round 0 chooses course 0 immediately.
If no such course exists, return false: the remaining subgraph contains a cycle. Otherwise mark the chosen course taken and decrement the count of every dependent in its adjacency list. Taking 0 in Example 1 changes need[1] from 1 to 0.
Restart the scan from label 0 each round. In Example 1 round 1 skips taken course 0 and chooses ready course 1; it has no dependents to update.
After all V rounds complete, return true. Example 1 ends with taken=[true,true]; the cyclic Example 2 instead fails its first scan.

Why It Works

The invariant is that need[c] equals the number of incoming edges from courses not yet taken. Initially it counts all prerequisites. Taking a zero-count course is safe because every prerequisite is already taken; decrementing each outgoing dependent maintains the invariant. The taken array prevents selecting the same zero-count course twice. If a scan finds no ready unfinished course, every remaining course has an incoming edge from another remaining course. Following such predecessors in a finite graph must revisit a course, proving a cycle. Conversely, a directed cycle can never lose its first edge because none of its courses can be taken first. Therefore selecting all V courses is equivalent to being able to finish the whole schedule.

Dry Run

Repeated Scan Kahn: variable states at each step
Event	round / scan c	pick	need [0,1]	taken [0,1]	action
build	not started	-	[0,1]	[false,false]	graph=[[1],[]]
scan	0 / 0	-1 to 0	[0,1]	[false,false]	0 is ready; break
take 0	0 / 0	0	[0,1]	[true,false]	mark taken
relax 0 to 1	0 / 0	0	[0,0]	[true,false]	need[1]: 1 to 0
scan	1 / 0	-1	[0,0]	[true,false]	skip taken 0
scan	1 / 1	-1 to 1	[0,0]	[true,false]	1 is ready; break
take 1	1 / 1	1	[0,0]	[true,true]	no outgoing edges
done	2 / -	-	[0,0]	[true,true]	all rounds complete; return true

Complexity Analysis

Time Complexity

O(V^2 + E)

Space Complexity

O(V + E)

Let V = numCourses and E = prerequisites.length. Building adjacency and indegrees costs O(V+E). Up to V rounds each scan up to V labels, giving O(V^2) worst-case scanning; even an empty graph checks 1+2+...+V labels as taken courses accumulate. Every outgoing edge is decremented once, giving total O(V^2+E) time. Adjacency contains V list objects and E edge entries; need and taken each store V values, so auxiliary space is O(V+E). The Boolean output is constant size and inputs are never modified. No recursion stack is used.

Code

Solution.java

1import java.util.*;2
3class Solution {4    public boolean canFinish(int numCourses, int[][] prerequisites) {5        List<List<Integer>> graph = new ArrayList<>();6        for (int i = 0; i < numCourses; i++) {7            graph.add(new ArrayList<>());8        }9        int[] need = new int[numCourses];10        for (int[] p : prerequisites) {11            graph.get(p[1]).add(p[0]);12            need[p[0]]++;13        }14        boolean[] taken = new boolean[numCourses];15        for (int round = 0; round < numCourses; round++) {16            int pick = -1;17            for (int c = 0; c < numCourses; c++) {18                if (!taken[c] && need[c] == 0) {19                    pick = c;20                    break;21                }22            }23            if (pick == -1) {24                return false;25            }26            // Mark before relaxing edges so the same ready course is never picked again.27            taken[pick] = true;28            for (int next : graph.get(pick)) {29                need[next]--;30            }31        }32        return true;33    }34}

Hints

Hint 1

Read each pair [a, b] as a directed edge from b to a, since b must come first.

Hint 2

Think topological order: repeatedly take a course whose prerequisites are all done, if one exists.

Hint 3

If you place fewer courses than numCourses, the unplaced remainder holds the cycle, so answer false.

Edge Cases

No prerequisites means every course is immediately takable, so the answer is true.
A single course with no prerequisites finishes trivially.
A self-loop pair such as [0, 0] is a one-course cycle and must return false.
A cycle in one component forces false even if all other components can finish.
Several courses can become ready together; choosing any ready course preserves feasibility.
A 2000-course chain is valid and uses no recursion; 5000 unique prerequisite pairs test the edge-count bound.

Common Mistakes and Interview Tips

Enqueueing a dependent after just one prerequisite finishes instead of waiting for its count to reach zero. A diamond dependency needs both incoming edges removed.
Counting only courses present in prerequisite pairs misses isolated courses; initialize all numCourses courses.
Leaving out taken in repeated scanning picks the same zero-count course repeatedly and can falsely report success.
Returning true because some courses finished: a disconnected cycle still blocks the remaining courses.
Using JavaScript queue.shift repeatedly can make dequeues quadratic; the head cursor keeps the queue approach linear.
Storing a to b while counting incoming prerequisites for a mixes orientations. Use b to a for these Kahn implementations. Reversing every edge consistently preserves cycle existence, but reverses scheduling meaning.
Interview tip: explain why a nonempty remainder with no zero-indegree course must contain a directed cycle; a shared prerequisite or an undirected cycle alone does not establish one.

Key Takeaway

Cycle questions on directed graphs reduce to topological sorting: Kahn drains prerequisite-free nodes first, and anything left over proves a cycle.