207. Course Schedule

mediumAsked at Canva

Detect whether a set of course prerequisites forms a cycle — Canva applies topological-sort cycle detection to their layer-dependency graph, where circular element references would cause infinite render loops in their design engine.

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

Problem

There are numCourses courses labeled 0 through 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, or false if a cycle exists.

Constraints

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= a_i, b_i < numCourses
All prerequisite pairs are unique

Examples

Example 1

Input

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

Output

true

Explanation: Take course 0 first, then course 1. No cycle.

Example 2

Input

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

Output

false

Explanation: Course 0 requires 1, and course 1 requires 0 — a cycle.

Approaches

1. DFS cycle detection (3-color marking)

Build an adjacency list; DFS from each unvisited node using three states (unvisited, in-progress, done) — a back-edge to an in-progress node signals a cycle.

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);
  }
  // 0 = unvisited, 1 = in-progress, 2 = done
  const state = new Array(numCourses).fill(0);
  function hasCycle(node) {
    if (state[node] === 1) return true;  // back edge
    if (state[node] === 2) return false; // already processed
    state[node] = 1;
    for (const neighbor of adj[node]) {
      if (hasCycle(neighbor)) return true;
    }
    state[node] = 2;
    return false;
  }
  for (let i = 0; i < numCourses; i++) {
    if (hasCycle(i)) return false;
  }
  return true;
}

Tradeoff:

2. Optimal (BFS topological sort — Kahn's algorithm)

Compute in-degrees; enqueue all zero-in-degree nodes; repeatedly dequeue a node and decrement neighbors' in-degrees, enqueuing any that reach zero — if all nodes are processed, no cycle exists.

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 > 0) {
    const node = queue.shift();
    processed++;
    for (const neighbor of adj[node]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }
  return processed === numCourses;
}

Tradeoff:

Canva-specific tips

Canva's rendering pipeline evaluates element dependencies in topological order — a frame element's content must render before the slide that references it. Interviewers will extend this to 'what if we need to return the actual order?' (Course Schedule II), so design your solution so the topological order falls out naturally. Kahn's BFS approach is generally preferred in production over DFS because it naturally surfaces the ordered sequence and avoids call-stack concerns on large graphs. Name Kahn's algorithm explicitly — it signals you know the canonical vocabulary.

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 Canva interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →