207. Course Schedule
mediumAsked at AirbnbGiven courses and prerequisites, determine if you can finish all courses. Airbnb asks this to test whether you map the problem to 'is the directed graph a DAG?' and reach for either Kahn's BFS or DFS 3-color.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Airbnb loops.
- Glassdoor (2026-Q1)— Airbnb new-grad and L4 onsite reports list Course Schedule as a recurring graph medium.
- Blind (2025-12)— Recurring in Airbnb backend interview reports.
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]]trueExample 2
numCourses = 2, prerequisites = [[1,0],[0,1]]falseApproaches
1. DFS 3-color cycle detection
DFS from each unvisited node. Mark gray on entry, black on exit. Gray hit during DFS = back edge -> cycle.
- Time
- O(V + E)
- Space
- O(V + E)
function canFinishDFS(numCourses, prerequisites) {
const graph = Array.from({ length: numCourses }, () => []);
for (const [a, b] of prerequisites) graph[b].push(a);
const WHITE = 0, GRAY = 1, BLACK = 2;
const color = new Array(numCourses).fill(WHITE);
function dfs(u) {
color[u] = GRAY;
for (const v of graph[u]) {
if (color[v] === GRAY) return false;
if (color[v] === WHITE && !dfs(v)) return false;
}
color[u] = BLACK;
return true;
}
for (let i = 0; i < numCourses; i++) if (color[i] === WHITE && !dfs(i)) return false;
return true;
}Tradeoff: Textbook cycle detection. Watch the recursion depth on adversarial inputs (fine at 2000 nodes).
2. Kahn's BFS (optimal)
Compute in-degrees. Queue 0-in-degree nodes. Pop, decrement neighbors, queue any that drop to 0. Processed-count vs numCourses gives the answer.
- Time
- O(V + E)
- Space
- O(V + E)
function canFinish(numCourses, prerequisites) {
const graph = Array.from({ length: numCourses }, () => []);
const indeg = new Array(numCourses).fill(0);
for (const [a, b] of prerequisites) { graph[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) {
const u = queue.shift();
processed++;
for (const v of graph[u]) if (--indeg[v] === 0) queue.push(v);
}
return processed === numCourses;
}Tradeoff: Iterative, no recursion-stack risk. Same complexity as DFS, often the cleaner whiteboard answer.
Airbnb-specific tips
Airbnb wants the framing said out loud: 'Prerequisites are directed edges; finishing all courses = topological order exists = no cycle.' Both DFS and BFS work; pick the one you can write bug-free. The framing is what's graded.
Common mistakes
- Edge direction reversed (prereq points to course, not course to prereq).
- Using just 'visited' in DFS — can't distinguish back edges from cross edges in a DAG.
- Forgetting to start DFS from every node (disconnected courses).
Follow-up questions
An interviewer at Airbnb may pivot to one of these next:
- Course Schedule II (LC 210) — return the order, not just feasibility.
- Undirected cycle detection — Union-Find or DFS-with-parent.
- Course Schedule IV (LC 1462) — transitive closure queries.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
DFS or BFS?
Both pass with clear narration. Kahn's BFS is naturally framed as topological sort; DFS 3-color is the textbook cycle detector. Pick what you write bug-free.
Why edge prereq -> course?
Topological-sort convention: edges point from 'must come first' to 'comes after'.
Free learning resources
Curated free links for this problem.