21. Course Schedule

mediumAsked at Wix

Detect cycles in a directed prerequisite graph to decide if all courses are completable — Wix applies the same topological-sort cycle check to component dependency graphs, build pipelines, and plugin load-order resolution in their platform.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-26

Problem

There are numCourses courses labeled 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a, b] means you must take course b before course a. Return true if you can finish all courses, false if a cycle makes it impossible.

Constraints

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
No duplicate edges, no self-loops

Examples

Example 1

Input

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

Output

true

Explanation: Take course 0 then course 1 — no cycle

Example 2

Input

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

Output

false

Explanation: Courses 0 and 1 depend on each other — cycle detected

Approaches

1. DFS cycle detection

Build an adjacency list, then DFS from each unvisited node. Track nodes on the current DFS path in a 'visiting' set; if you revisit a node on the current path, a cycle exists.

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

function canFinish(numCourses, prerequisites) {
  const adj = Array.from({ length: numCourses }, () => []);
  for (const [a, b] of prerequisites) {
    adj[b].push(a);
  }

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

  function hasCycle(node) {
    if (state[node] === VISITING) return true;
    if (state[node] === VISITED) return false;
    state[node] = VISITING;
    for (const neighbor of adj[node]) {
      if (hasCycle(neighbor)) return true;
    }
    state[node] = VISITED;
    return false;
  }

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

Tradeoff:

2. Kahn's algorithm (BFS topological sort)

Compute in-degrees for all nodes. Enqueue nodes with in-degree 0. Process the queue, decrementing neighbors' in-degrees; if all nodes are processed, the graph is acyclic.

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

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

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

  const queue = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  let processed = 0;
  while (queue.length) {
    const node = queue.shift();
    processed++;
    for (const neighbor of adj[node]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  return processed === numCourses;
}

Tradeoff:

Wix-specific tips

Wix's platform team deals with plugin graphs where circular dependencies crash the editor at boot. Mentioning that Kahn's algorithm gives you a valid load order for free — not just a cycle flag — shows you're thinking about the production use case, not just the algorithmic result.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Course Schedule and other Wix interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →