Course Schedule

MediumGraph DFS BFS

A university's degree planner checks new curricula for mistakes. A curriculum has numCourses courses numbered from 0 to numCourses - 1, and each pair prerequisites[i] = [a, b] says that course b has to be passed before a student may enrol in course a.

Return true if a student could pass every course in some order that respects all of the prerequisites, and false if the rules make that impossible.

Example 1

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

Explanation: One valid order is 0, 1, 2, 3, 4: course 2 needs both 0 and 1, and courses 3 and 4 each need 2.

Example 2

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

Explanation: Course 0 needs 1, course 1 needs 2 and course 2 needs 0, so none of them can be taken first.

Example 3

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

Explanation: Without prerequisites, the courses can be taken in any order.

Constraints

numCourses is between 1 and 2000.
There are at most 5000 prerequisite pairs, and no pair appears twice.
In every pair [a, b], both courses exist and a is different from b.

Follow-up: Return an actual order in which to take the courses (or an empty array if none exists).

💡 Hint 1

Model courses as nodes and each prerequisite [a, b] as a directed edge b → a. When is it impossible to finish?

💡 Hint 2

All courses can be finished exactly when the graph has no cycle.

💡 Hint 3

Kahn's algorithm: repeatedly take a course with no remaining prerequisites and remove its outgoing edges. If you manage to take all of them, there is no cycle. (A DFS with three node colours works too.)

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Cycle detection with a topological sort (Kahn's algorithm). Build adjacency lists for edges b → a and count each course's incoming edges (its unmet prerequisites). Start a queue with every course whose count is 0. Each time you take a course from the queue, decrement the count of every course that depends on it and enqueue those that reach 0. If the number of courses taken equals numCourses, the graph is acyclic and everything can be finished. Courses on a cycle never reach 0, so they are never taken.

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

function canFinish(numCourses, prerequisites) {
  const next = Array.from({ length: numCourses }, () => []);
  const indegree = new Array(numCourses).fill(0);
  for (const [course, pre] of prerequisites) {
    next[pre].push(course);
    indegree[course]++;
  }
  const queue = [];
  for (let i = 0; i < numCourses; i++) if (indegree[i] === 0) queue.push(i);
  let taken = 0;
  for (let h = 0; h < queue.length; h++) {
    taken++;
    for (const c of next[queue[h]]) {
      if (--indegree[c] === 0) queue.push(c);
    }
  }
  return taken === numCourses;
}

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> next = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) next.add(new ArrayList<>());
        int[] indegree = new int[numCourses];
        for (int[] p : prerequisites) {
            next.get(p[1]).add(p[0]);
            indegree[p[0]]++;
        }
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) if (indegree[i] == 0) queue.add(i);
        int taken = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            taken++;
            for (int c : next.get(course)) {
                if (--indegree[c] == 0) queue.add(c);
            }
        }
        return taken == numCourses;
    }
}

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
function canFinish(numCourses, prerequisites) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit