Skip to main content

207. Course Schedule

mediumAsked at Twilio

Course Schedule is Twilio's cycle-detection probe: given numCourses and a list of prerequisite pairs, decide if all courses can be finished. The grading rubric weighs whether you frame it as 'does the directed graph have a cycle?' and use either Kahn's BFS topological sort or DFS with three-color marking.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Twilio loops.

  • Glassdoor (2026-Q1)— Reported in Twilio backend SWE on-site rounds, especially for platform and infra teams.
  • LeetCode Discuss (2025-12)— Cited in Twilio interview reports as a 'translate the problem to a graph' question.

Problem

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai. Return true if you can finish all courses. Otherwise, return false.

Constraints

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • All the pairs prerequisites[i] are unique.

Examples

Example 1

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

Explanation: Take 0 then 1.

Example 2

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

Explanation: Cycle — neither course can be taken first.

Approaches

1. Naive simulation — try every permutation (rejected)

Try every permutation of courses; for each, verify prerequisites are met.

Time
O(n! * m)
Space
O(n)
function canFinishBrute(numCourses, prerequisites) {
  const order = [];
  for (let i = 0; i < numCourses; i++) order.push(i);
  const tryPermutations = (start) => {
    if (start === order.length) {
      const pos = new Array(numCourses);
      order.forEach((c, i) => pos[c] = i);
      return prerequisites.every(([a, b]) => pos[b] < pos[a]);
    }
    for (let i = start; i < order.length; i++) {
      [order[start], order[i]] = [order[i], order[start]];
      if (tryPermutations(start + 1)) return true;
      [order[start], order[i]] = [order[i], order[start]];
    }
    return false;
  };
  return tryPermutations(0);
}

Tradeoff: Factorial blowup — TLE for n > ~10. Useful only as a baseline to mention before pivoting to topological sort.

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

Compute in-degrees, queue every node with in-degree 0, repeatedly dequeue and decrement neighbors' in-degrees. If processed count == numCourses, no cycle.

Time
O(V + E)
Space
O(V + E)
function canFinish(numCourses, prerequisites) {
  const adj = Array.from({ length: numCourses }, () => []);
  const inDeg = new Array(numCourses).fill(0);
  for (const [a, b] of prerequisites) {
    adj[b].push(a);
    inDeg[a]++;
  }
  const queue = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDeg[i] === 0) queue.push(i);
  }
  let processed = 0;
  while (queue.length > 0) {
    const node = queue.shift();
    processed++;
    for (const next of adj[node]) {
      inDeg[next]--;
      if (inDeg[next] === 0) queue.push(next);
    }
  }
  return processed === numCourses;
}

Tradeoff: Kahn's gives both the cycle-detect answer and (for LC 210) a valid topological order for free. The queue.shift() is O(n) — fine for the constraints; use an index pointer for tighter perf.

3. DFS with three-color marking (alternative)

DFS from each node; track nodes as WHITE (unvisited), GRAY (in current stack), BLACK (finished). A GRAY node visited again means a cycle.

Time
O(V + E)
Space
O(V + E)
function canFinishDFS(numCourses, prerequisites) {
  const adj = Array.from({ length: numCourses }, () => []);
  for (const [a, b] of prerequisites) adj[b].push(a);
  const color = new Array(numCourses).fill(0); // 0=white, 1=gray, 2=black
  const dfs = (node) => {
    if (color[node] === 1) return false; // cycle
    if (color[node] === 2) return true;  // already finished
    color[node] = 1;
    for (const next of adj[node]) {
      if (!dfs(next)) return false;
    }
    color[node] = 2;
    return true;
  };
  for (let i = 0; i < numCourses; i++) {
    if (!dfs(i)) return false;
  }
  return true;
}

Tradeoff: Same asymptotics; DFS uses recursion-stack space proportional to graph depth. Easier to extend to 'find a cycle' (return the GRAY ancestors); Kahn's is easier to extend to 'return a valid order'.

Twilio-specific tips

Twilio reviewers grade whether you can translate 'can all courses be taken?' into 'does this directed graph have a cycle?' within 60 seconds. State the graph model out loud (nodes = courses, edges = b -> a meaning 'b is a prereq of a'), then offer both Kahn's and DFS — the choice depends on the follow-up. Kahn's is cleaner if you'll later be asked for a valid order (LC 210).

Common mistakes

  • Reversing the edge direction — building edges a -> b instead of b -> a changes the answer.
  • In DFS, forgetting the three-color distinction and using a simple visited set — that fails to detect cycles in the current recursion path.
  • Returning false the first time you fail to extend the queue, instead of checking processed == numCourses at the end.

Follow-up questions

An interviewer at Twilio may pivot to one of these next:

  • Can you also return the order, not just yes/no (LC 210)? (Kahn's gives the order for free — collect dequeued nodes.)
  • What if prerequisites had optional alternatives (e.g., 'course X needs Y OR Z')? (AND-OR graph; the cycle detection generalizes to alternating-quantifier reachability.)
  • How would you handle 10^9 nodes and 10^9 edges? (Distributed BFS — Pregel-style frontier expansion across a cluster.)

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why does in-degree 0 correspond to 'can be taken now'?

Because in-degree 0 means no remaining prereqs. Kahn's invariant is: dequeue a course that has no remaining prereqs, mark it taken, and decrement its outgoing courses' prereq counts.

Why does Kahn's terminate correctly on cycles?

Because every node in a cycle has in-degree >= 1 from another cycle node — none of them ever reach in-degree 0, so they never enter the queue. Processed count stays below numCourses.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →