Skip to main content

207. Course Schedule

mediumAsked at Robinhood

Given a graph of course prerequisites, determine if it's possible to finish all courses. Robinhood asks this for cycle-detection on a directed graph — the same shape that pops up in dependency resolution for service deploys and ETL DAGs.

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

Source citations

Public interview reports confirming this problem appears in Robinhood loops.

  • Glassdoor (2026-Q1)— Robinhood SWE-II onsite reports list Course Schedule and the topological-order variant as recurring graph problems.
  • Blind (2025-09)— Robinhood backend trip reports cite cycle-detection on DAGs as a thematic favorite.

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: 0 -> 1 -> 0.

Approaches

1. DFS with three-color visited

DFS with WHITE/GRAY/BLACK marking. Encountering a GRAY (in-progress) node means a 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 hasCycle(u) {
    if (color[u] === GRAY) return true;
    if (color[u] === BLACK) return false;
    color[u] = GRAY;
    for (const v of graph[u]) {
      if (hasCycle(v)) return true;
    }
    color[u] = BLACK;
    return false;
  }
  for (let i = 0; i < numCourses; i++) {
    if (hasCycle(i)) return false;
  }
  return true;
}

Tradeoff: Standard DFS cycle detection. Three colors are necessary — two colors (visited/unvisited) can't distinguish 'on current path' from 'already finished'.

2. Kahn's algorithm (BFS topological sort)

Compute in-degrees. Queue all zero-in-degree nodes. Process: decrement neighbors' in-degree, enqueue when zero. If all nodes processed, no 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 processed = 0;
  let head = 0;
  while (head < queue.length) {
    const u = queue[head++];
    processed++;
    for (const v of graph[u]) {
      if (--inDegree[v] === 0) queue.push(v);
    }
  }
  return processed === numCourses;
}

Tradeoff: Same O(V + E). Cleaner because it doubles as the actual topological order (LC 210's answer is just the queue array). Robinhood interviewers prefer Kahn's when they signal the topological-order follow-up is coming.

Robinhood-specific tips

Robinhood interviewers usually follow up with LC 210 (return the topological order, not just feasibility). Use Kahn's algorithm — the queue's processing order IS the answer to LC 210, so you get a two-for-one. If you use DFS, you'd need to post-order push to a stack which is more error-prone under pressure.

Common mistakes

  • Building the graph in the wrong direction — the edge [a, b] means b -> a (b is prereq of a), not a -> b.
  • Using only two colors in DFS — can't distinguish a cycle from a re-visit of an already-completed node.
  • Forgetting to count processed nodes in Kahn's — you need the final == numCourses comparison.

Follow-up questions

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

  • Course Schedule II (LC 210) — return the order, not just feasibility.
  • Course Schedule III (LC 630) — scheduling with deadlines and durations; greedy + heap.
  • Alien Dictionary (LC 269) — topological sort applied to alphabet ordering.
  • Detect cycle in undirected graph (Union-Find).

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 three colors and not two?

Two colors (visited/unvisited) can't tell whether you're re-entering a node on the current DFS path (which means cycle) or one already fully explored (which means safe). The GRAY (on-path) state distinguishes them.

Kahn's vs DFS — which does Robinhood prefer?

Both score equally. Kahn's is a natural pick if you expect the topological-order follow-up. DFS is cleaner code if you only need yes/no.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →