Skip to main content

71. Course Schedule

mediumAsked at Reddit

Determine if you can finish all courses given prerequisite pairs (cycle detection in a DAG). Reddit uses this to test topological-sort intuition — the same shape used when validating cross-shard data-migration dependency graphs.

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit infra-team graph 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] = [a_i, b_i] indicates that you must take course b_i first if you want to take course a_i. Return true if you can finish all courses. Otherwise, return false.

Constraints

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= a_i, b_i < 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 with three colors

WHITE/GRAY/BLACK. Detect back-edge = GRAY revisit.

Time
O(V + E)
Space
O(V + E)
function canFinish(n, prereqs) {
  const adj = Array.from({length: n}, () => []);
  for (const [a, b] of prereqs) adj[b].push(a);
  const color = new Array(n).fill(0); // 0=white, 1=gray, 2=black
  function dfs(u) {
    if (color[u] === 1) return false;
    if (color[u] === 2) return true;
    color[u] = 1;
    for (const v of adj[u]) if (!dfs(v)) return false;
    color[u] = 2;
    return true;
  }
  for (let i = 0; i < n; i++) if (!dfs(i)) return false;
  return true;
}

Tradeoff: DFS-based cycle detection.

2. Kahn's algorithm (BFS topo sort) (optimal)

Compute in-degrees. Push 0-in-degree nodes to queue. Pop, reduce neighbors' in-degree; push when they hit 0. If processed count != n, cycle exists.

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) {
    const u = queue.shift();
    processed++;
    for (const v of adj[u]) if (--inDeg[v] === 0) queue.push(v);
  }
  return processed === numCourses;
}

Tradeoff: Iterative, no recursion stack risk.

Reddit-specific tips

Reddit interviewers want Kahn's algorithm — it gives the topological order for free and avoids recursion. Bonus signal: mention that LC 210 ('Course Schedule II') asks for the order itself.

Common mistakes

  • Building the adjacency in the wrong direction (b -> a, not a -> b).
  • Returning early after first 0 in-degree node.
  • Not handling disconnected DAGs.

Follow-up questions

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

  • Course Schedule II (LC 210) — return the order.
  • Alien dictionary (LC 269) — topo sort on characters.
  • Find all eventually safe states (LC 802).

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 Kahn's over DFS?

Same complexity but iterative — no stack overflow for deep graphs. Also gives the order directly.

How does cycle detection work in Kahn's?

If a cycle exists, none of its nodes ever reach in-degree 0. The processed count falls short of n.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →