Course Schedule — Practice

Problem

There are numCourses courses labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a, b] indicates you must take course b before course a.

Return true if you can finish all courses (no cycle), false otherwise.

Examples

Example 1

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

Output: true

Explanation: Take 0 then 1.

Example 2

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

Output: false

Explanation: Cycle: 0→1→0.

Constraints

•1 <= numCourses <= 2000
•0 <= prerequisites.length <= 5000

Hints

Hint 1

This is cycle detection in a directed graph — if a cycle exists among the prerequisites, no valid course order can exist.

Hint 2

Kahn's algorithm (BFS): repeatedly remove nodes with zero remaining in-degree; if a cycle exists, some nodes never reach in-degree zero and are never removed.

Hint 3

A DFS-based alternative marks each node's state as unvisited / currently-visiting / fully-visited — revisiting a currently-visiting node mid-DFS is exactly what detecting a 'back edge' (a cycle) looks like.

Solutions

public boolean canFinish(int numCourses, int[][] prerequisites) {
    int[] inDegree = new int[numCourses];
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
    for (int[] pre : prerequisites) {
        adj.get(pre[1]).add(pre[0]);
        inDegree[pre[0]]++;
    }
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++)
        if (inDegree[i] == 0) queue.offer(i);
    int processed = 0;
    while (!queue.isEmpty()) {
        int course = queue.poll();
        processed++;
        for (int next : adj.get(course)) {
            if (--inDegree[next] == 0) queue.offer(next);
        }
    }
    return processed == numCourses;
}

Time: O(V+E) · Space: O(V+E)