Course Schedule

Examples

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

Take course 0 first, then course 1. No conflict.

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

Course 1 needs course 0 first, but course 0 needs course 1 first - neither can ever go first.

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

One valid order is 0, 1, 2, 3 - course 0 has no prerequisites, and every later course's prerequisites come before it.

Constraints

• 1 <= numCourses <= 2000

• 0 <= prerequisites.length <= 5000

• prerequisites[i].length == 2

• There are no duplicate prerequisite pairs.

Approach

Build a directed graph where an edge from b to a means "b must come before a." Now finishing all courses is possible exactly when this graph has no cycle - if there were a cycle, every course on it would be stuck waiting for another course on the very same cycle.

One way to check for a cycle is a DFS that tracks each node's state: unvisited, currently being explored (on the active recursion path), or fully done (already confirmed cycle-free). If the DFS ever walks into a node that is "currently being explored," that's a back-edge into the current path - a cycle - so the answer is false. If DFS finishes exploring every node without ever doing that, there's no cycle and the answer is true.

A different, non-recursive way to reach the same conclusion is Kahn's algorithm: repeatedly peel off courses that currently have no remaining prerequisites. If you can eventually peel off every course this way, there's no cycle.

Solutions

Brute Force - Try Every Ordering

Finishing all courses is possible exactly when some ordering of the courses respects every prerequisite pair. The most naive way to check that is to literally generate every possible ordering of the courses and test each one against every prerequisite pair, stopping as soon as one ordering works.

function canFinish(numCourses, prerequisites) {
  const courses = Array.from({ length: numCourses }, (_, i) => i);

  function isValidOrder(order) {
    const position = new Map();
    order.forEach((course, index) => position.set(course, index));

    for (const [a, b] of prerequisites) {
      if (position.get(b) > position.get(a)) return false; // b must come before a
    }
    return true;
  }

  function permute(start) {
    if (start === courses.length) {
      return isValidOrder(courses);
    }
    for (let i = start; i < courses.length; i++) {
      [courses[start], courses[i]] = [courses[i], courses[start]];
      if (permute(start + 1)) return true;
      [courses[start], courses[i]] = [courses[i], courses[start]];
    }
    return false;
  }

  return permute(0);
}

Time: O(n! × (n + p)) - n! orderings, each checked against p prerequisite pairs · Space: O(n)

Optimal - DFS Cycle Detection

Build an adjacency list from the prerequisites, then DFS from every course, tagging each node as visiting (on the current recursion path) or done (fully explored, no cycle found through it). If DFS ever reaches a node already tagged visiting, that's a cycle, so finishing is impossible.

function canFinish(numCourses, prerequisites) {
  const graph = Array.from({ length: numCourses }, () => []);
  for (const [a, b] of prerequisites) {
    graph[b].push(a); // b must be taken before a
  }

  const UNVISITED = 0, VISITING = 1, DONE = 2;
  const state = new Array(numCourses).fill(UNVISITED);

  function hasCycle(course) {
    if (state[course] === VISITING) return true; // back edge into current path
    if (state[course] === DONE) return false; // already confirmed safe

    state[course] = VISITING;
    for (const next of graph[course]) {
      if (hasCycle(next)) return true;
    }
    state[course] = DONE;
    return false;
  }

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

Time: O(V + E) - every course and every prerequisite edge is visited once · Space: O(V + E) for the adjacency list, plus O(V) for the state array and recursion stack