17. Course Schedule

Q: Why does Kahn's algorithm detect cycles?

Because nodes in a cycle never have in-degree 0 — they always depend on another cycle member. They never enter the queue, so the final visited count is less than n.

Q: Which is faster — DFS or Kahn's?

Both are O(V + E) in theory. In practice, Kahn's is iterative and avoids the function-call overhead of recursive DFS. For production-grade DAG validation at Palantir's scale, Kahn's wins.

mediumAsked at Palantir

Given n courses with prerequisite pairs, determine if you can finish all courses. Palantir asks this because it's literally the same cycle-detection check their Foundry build engine runs before scheduling an ETL DAG — any cycle and the pipeline rejects the build.

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

Source citations

Public interview reports confirming this problem appears in Palantir loops.

Glassdoor (2026-Q1)— Palantir FDE on-site — explicitly framed as 'ETL DAG validation'.
Blind (2025-11)— Two candidates in the same week reported this question.
Reddit r/cscareerquestions (2026-02)— Tagged 'Palantir DAG 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 course 0, then course 1.

Example 2

Input

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

Output

false

Explanation: Cycle: 1 needs 0, 0 needs 1.

Approaches

1. DFS with white/gray/black coloring

DFS each node; mark in-progress (gray) vs done (black). If you revisit a gray node, you've found a back-edge — cycle.

Time: O(V + E)
Space: O(V + E)

function canFinish(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) {
    if (color[u] === GRAY) return false;
    if (color[u] === BLACK) return true;
    color[u] = GRAY;
    for (const v of graph[u]) if (!dfs(v)) return false;
    color[u] = BLACK;
    return true;
  }
  for (let i = 0; i < numCourses; i++) if (!dfs(i)) return false;
  return true;
}

Tradeoff: Classic but recursive — deep graphs (numCourses up to 2000) can blow the stack. Use the iterative version below for production.

2. Kahn's algorithm (BFS topological sort)

Compute in-degree for every node. Enqueue all zero-in-degree nodes. Pop, decrement neighbors' in-degree, enqueue new zeros. If you visit fewer than n nodes, there's a cycle.

Time: O(V + E)
Space: O(V + E)

function canFinish(numCourses, prerequisites) {
  const graph = Array.from({length: numCourses}, () => []);
  const inDegree = new Array(numCourses).fill(0);
  for (const [a, b] of prerequisites) {
    graph[b].push(a);
    inDegree[a]++;
  }
  const queue = [];
  for (let i = 0; i < numCourses; i++) if (inDegree[i] === 0) queue.push(i);
  let visited = 0;
  while (queue.length) {
    const u = queue.shift();
    visited++;
    for (const v of graph[u]) {
      if (--inDegree[v] === 0) queue.push(v);
    }
  }
  return visited === numCourses;
}

Tradeoff: Iterative — safe on any graph size. The Kahn's-by-name signal is what Palantir wants; it's the same algorithm their scheduler uses.

Palantir-specific tips

Palantir grades this on two axes: (1) do you know Kahn's algorithm by name, and (2) can you state the in-degree invariant before coding. Connect it to Foundry directly: each pipeline transform is a node, dependencies are edges, and the scheduler must topologically order them — a cycle means the build is invalid. Bonus signal: mention that if you want to RETURN the order (not just yes/no), Kahn's gives it for free.

Common mistakes

Building the graph in the wrong direction — [a, b] means a depends on b, so the edge is b → a, not a → b.
Forgetting to handle disconnected components — Kahn's handles them naturally, but DFS must loop over all start nodes.
Confusing 'visited count < numCourses' as the cycle signal in DFS — that's only valid for Kahn's.

Follow-up questions

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

Course Schedule II (LC 210) — return the order.
Course Schedule III (LC 630) — with deadlines, heap-based.
Alien Dictionary (LC 269) — topological sort applied to characters.

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 Kahn's algorithm detect cycles?

Because nodes in a cycle never have in-degree 0 — they always depend on another cycle member. They never enter the queue, so the final visited count is less than n.

Which is faster — DFS or Kahn's?

Both are O(V + E) in theory. In practice, Kahn's is iterative and avoids the function-call overhead of recursive DFS. For production-grade DAG validation at Palantir's scale, Kahn's wins.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →