207. Course Schedule

Q: DFS or Kahn's — which should I default to?

If the next question is 'now return the order', use Kahn's because the dequeue order IS the topological order. If you only need true/false, DFS three-coloring is shorter.

Q: Why does the three-color trick work?

GRAY = 'I'm currently exploring descendants of this node.' Reaching a GRAY neighbor means you've looped back to an ancestor on the current path, which is the definition of a back-edge = a cycle. BLACK nodes are safe because we've already verified their subtree is cycle-free.

mediumAsked at Cisco

Course Schedule is Cisco's go-to cycle-detection problem because dependency graphs sit at the heart of every router-config validator and build-system the company ships. The interviewer is checking whether you reach for Kahn's algorithm or DFS three-coloring, and whether you can explain why a cycle = a circular dependency.

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

Source citations

Public interview reports confirming this problem appears in Cisco loops.

Glassdoor (2026-Q1)— Cisco Software Engineer onsite reports list Course Schedule as a graph round.
Blind (2025-09)— Cisco SDE-II candidates report this as the canonical topological-sort question.

Problem

There are 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 pairs 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: Course 0 needs course 1 and vice-versa — that's a cycle.

Approaches

1. Brute-force recursive check with visited tracking

For each course, recursively walk its prereqs. If we revisit a node already on the current path, that's a cycle.

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

function canFinishBrute(numCourses, prereqs) {
  const graph = Array.from({ length: numCourses }, () => []);
  for (const [a, b] of prereqs) graph[a].push(b);
  function hasCycle(node, visiting) {
    if (visiting.has(node)) return true;
    visiting.add(node);
    for (const next of graph[node]) {
      if (hasCycle(next, visiting)) return true;
    }
    visiting.delete(node);
    return false;
  }
  for (let i = 0; i < numCourses; i++) {
    if (hasCycle(i, new Set())) return false;
  }
  return true;
}

Tradeoff: Re-walks the graph from every node — quadratic-ish on dense graphs. Use only to show the interviewer you understand the cycle-on-path invariant before optimizing.

2. DFS three-coloring (optimal)

Mark each node WHITE (unseen) → GRAY (on the current DFS path) → BLACK (fully processed). If you ever hit a GRAY neighbor, you've found a back-edge = a cycle.

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

function canFinish(numCourses, prereqs) {
  const graph = Array.from({ length: numCourses }, () => []);
  for (const [a, b] of prereqs) graph[a].push(b);
  const WHITE = 0, GRAY = 1, BLACK = 2;
  const color = new Array(numCourses).fill(WHITE);
  function dfs(node) {
    if (color[node] === GRAY) return false;
    if (color[node] === BLACK) return true;
    color[node] = GRAY;
    for (const next of graph[node]) {
      if (!dfs(next)) return false;
    }
    color[node] = BLACK;
    return true;
  }
  for (let i = 0; i < numCourses; i++) {
    if (!dfs(i)) return false;
  }
  return true;
}

Tradeoff: Linear in graph size. The three-color invariant is the standard way to phrase cycle detection on directed graphs and shows up verbatim in CLRS — interviewers expect this vocabulary.

3. Kahn's algorithm (BFS topological sort)

Repeatedly peel off nodes with in-degree zero. If you peel off fewer than numCourses, you have a cycle.

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

function canFinishKahn(numCourses, prereqs) {
  const graph = Array.from({ length: numCourses }, () => []);
  const indeg = new Array(numCourses).fill(0);
  for (const [a, b] of prereqs) {
    graph[b].push(a);
    indeg[a]++;
  }
  const queue = [];
  for (let i = 0; i < numCourses; i++) if (indeg[i] === 0) queue.push(i);
  let taken = 0;
  while (queue.length) {
    const node = queue.shift();
    taken++;
    for (const next of graph[node]) {
      if (--indeg[next] === 0) queue.push(next);
    }
  }
  return taken === numCourses;
}

Tradeoff: Same Big-O, but iterative — no recursion-depth worry. Cisco interviewers often prefer Kahn's because it generalizes directly to Course Schedule II (return the order).

Cisco-specific tips

Cisco loves the framing 'a directed graph is satisfiable iff it has a topological order iff it is acyclic.' Say that sentence early and the interviewer relaxes. If they push back with 'what if you also have to return the schedule?', pivot to Kahn's and explain that the order you dequeue nodes IS the topological order. Bring up real-world: protocol dependency in IOS feature trees, build-system ordering — Cisco loves the engineering connection.

Common mistakes

Mixing up the direction of the edge — '[a, b] means b is a prereq of a' so the edge goes b → a (or you build the reverse adjacency, but be consistent).
Using a single visited Set instead of three colors — you can't distinguish 'on current path' from 'already processed', so you'll false-positive cycles in DAGs with shared subgraphs.
Forgetting that the graph can be disconnected — must loop the outer DFS over all nodes, not just node 0.

Follow-up questions

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

Return the schedule itself, not just true/false. (LC 210 Course Schedule II — Kahn's or DFS post-order reversed.)
Minimum number of semesters to finish all courses. (LC 1136 — Kahn's with level tracking.)
Parallel courses with K courses per semester. (LC 1494 — Kahn's + bitmask DP.)

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 Kahn's — which should I default to?

If the next question is 'now return the order', use Kahn's because the dequeue order IS the topological order. If you only need true/false, DFS three-coloring is shorter.

Why does the three-color trick work?

GRAY = 'I'm currently exploring descendants of this node.' Reaching a GRAY neighbor means you've looped back to an ancestor on the current path, which is the definition of a back-edge = a cycle. BLACK nodes are safe because we've already verified their subtree is cycle-free.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →