207. Course Schedule
mediumAsked at TwilioCourse 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 Sam K., 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 <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= ai, bi < numCoursesAll the pairs prerequisites[i] are unique.
Examples
Example 1
numCourses = 2, prerequisites = [[1,0]]trueExplanation: Take 0 then 1.
Example 2
numCourses = 2, prerequisites = [[1,0],[0,1]]falseExplanation: 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.
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.