Skip to main content

207. Course Schedule

mediumAsked at Airbnb

Given 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 Alex Chen, 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 <= 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

Example 2

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

Approaches

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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →