Course Schedule

return true if we can finish all the courses

Course Schedule

Problem

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

Return true if you can finish all courses. Otherwise, return false.

Examples

Example 1

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

• To take course 1, you must finish course 0 first.
• Take 0, then 1. This is possible.

Example 2

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

• Course 1 needs course 0, and course 0 needs course 1.
• Each course waits for the other, so it is impossible.

Constraints

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

Main Idea

Think of each course as a node and each prerequisite as a directed edge b -> a (take b before a).

• If the graph has a cycle, some courses wait for each other forever. The answer is false.
• If the graph has no cycle, we can find a valid order. The answer is true.

So the problem becomes: does this directed graph have a cycle? This is the same idea as the task order problem, where a topological sort fails when there is a cycle.

Solution 1: Kahn's Algorithm (BFS)

We take courses that have no waiting prerequisites, and finish them one by one.

• In-degree: the number of prerequisites a course still waits for.
• Start with all courses that have in-degree 0.
• When a course is finished, lower the in-degree of every course that depends on it.
• If an in-degree becomes 0, that course is ready, so add it to the queue.
• At the end, if we finished all courses, there is no cycle.

var canFinish = function (numCourses, prerequisites) {
    const graph = Array.from({ length: numCourses }, () => []);
    const indegree = new Array(numCourses).fill(0);

    // edge b -> a: finish b before a
    for (const [a, b] of prerequisites) {
        graph[b].push(a);
        indegree[a]++;
    }

    // start with courses that have no prerequisites
    const queue = [];
    for (let i = 0; i < numCourses; i++) {
        if (indegree[i] === 0) queue.push(i);
    }

    let head = 0; // pointer instead of shift(), so each pop is O(1)
    let finished = 0;

    while (head < queue.length) {
        const course = queue[head++];
        finished++;

        for (const next of graph[course]) {
            indegree[next]--;

            // all prerequisites of "next" are done
            if (indegree[next] === 0) {
                queue.push(next);
            }
        }
    }

    // if we finished every course, there is no cycle
    return finished === numCourses;
};

How the Code Works

• Step 1: graph[b] holds the courses that need b. indegree[a] counts the prerequisites of a.
• Step 2: Courses with in-degree 0 go into the queue first.
• Step 3: For each course taken from the queue, we count it as finished and lower the in-degree of its dependents.
• Step 4: In a cycle, the courses never reach in-degree 0, so they never enter the queue. Then finished < numCourses, and we return false.

Dry Run

Let us take numCourses = 2 and prerequisites = [[1,0],[0,1]].

• Edges: 0 -> 1 and 1 -> 0.
• In-degrees: indegree[0] = 1 and indegree[1] = 1.
• No course has in-degree 0, so the queue is empty.
• finished = 0, which is not equal to 2. The answer is false.

Now let us take prerequisites = [[1,0]].

finished = 2 = numCourses, so the answer is true.

Complexity

• Time Complexity: O(V + E)
  • V is the number of courses and E is the number of prerequisites.
  • We build the graph in O(V + E), and each course and edge is processed once.
• Space Complexity: O(V + E)
  • The graph stores E edges, and the arrays and queue hold V values.

Solution 2: DFS with Cycle Detection

We walk deep into the graph. We track each course in one of three states:

• 0: not visited yet.
• 1: in progress, so it is on the current DFS path.
• 2: done, so it and everything after it were checked and are safe.

If we reach a course that is in progress, we came back to the current path. That is a cycle.

var canFinish = function (numCourses, prerequisites) {
    const graph = Array.from({ length: numCourses }, () => []);

    for (const [a, b] of prerequisites) {
        graph[b].push(a);
    }

    const state = new Array(numCourses).fill(0);

    // returns true if a cycle is found
    function hasCycle(course) {
        if (state[course] === 1) return true;  // back on the current path
        if (state[course] === 2) return false; // already checked and safe

        state[course] = 1; // in progress

        for (const next of graph[course]) {
            if (hasCycle(next)) return true;
        }

        state[course] = 2; // done
        return false;
    }

    for (let i = 0; i < numCourses; i++) {
        if (hasCycle(i)) return false;
    }

    return true;
};

How the Code Works

• We start a DFS from every course, because the graph may have separate parts.
• A state of 1 means the course is on the current path. Seeing it again means a cycle.
• A state of 2 means we already checked it, so we skip it. This keeps the time linear.
• If any DFS finds a cycle, we return false. Otherwise, we return true.

Complexity

• Time Complexity: O(V + E)
  • Each course is fully explored once, and each edge is checked once.
• Space Complexity: O(V + E)
  • The graph and the state array use this space.
  • The recursion stack can go as deep as V, which is at most 2000 here, so it is safe.

Comparison

Summary

• Courses and prerequisites form a directed graph. You can finish all courses only if the graph has no cycle.
• Kahn's algorithm repeatedly takes courses with in-degree 0. If it finishes all courses, there is no cycle.
• DFS marks courses as not visited, in progress or done. Reaching an in-progress course means a cycle.
• Both solutions run in O(V + E) time and use O(V + E) space.
• The next problem, Course Schedule II, asks for the actual order. The Kahn's solution gives it directly: the order in which courses leave the queue.