18. Course Schedule

mediumAsked at ServiceNow

Determine if you can finish all courses given prerequisite dependencies — a cycle-detection problem on a directed graph. ServiceNow asks this because workflow dependency graphs in their automation engine must be acyclic; detecting cycles is a core interview signal.

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

Source citations

Public interview reports confirming this problem appears in ServiceNow loops.

LeetCode Discuss (2026)— Multiple ServiceNow candidates report this in SDE-II onsite graph rounds.
Blind (2025)— Cited as a ServiceNow favorite graph question for mid-level roles.

Problem

There are numCourses courses labeled 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, or false if there is a cycle.

Constraints

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
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 — no cycle.

Example 2

Input

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

Output

false

Explanation: Courses 0 and 1 depend on each other — cycle detected.

Approaches

1. DFS with visited coloring

Three-color DFS: white (unvisited), gray (in current DFS path), black (fully processed). A back edge to a gray node signals a 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);
  // 0=unvisited, 1=in-stack, 2=done
  const state = new Array(numCourses).fill(0);
  function hasCycle(node) {
    if (state[node] === 1) return true;  // back edge
    if (state[node] === 2) return false; // already safe
    state[node] = 1;
    for (const nei of graph[node]) if (hasCycle(nei)) return true;
    state[node] = 2;
    return false;
  }
  for (let i = 0; i < numCourses; i++) if (hasCycle(i)) return false;
  return true;
}

Tradeoff: O(V+E) — optimal. Recursive DFS may stack-overflow for V=2000; iterative version is safer in production but harder to write under time pressure.

2. Topological sort via Kahn's algorithm (BFS + in-degree)

Build in-degree counts for each node. Enqueue all nodes with in-degree 0. Process the queue, reducing neighbors' in-degrees; enqueue when a neighbor hits 0. If all nodes are processed, no cycle exists. ServiceNow interviewers appreciate this because it mirrors the execution order of a workflow engine.

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;
  while (queue.length) {
    const node = queue.shift();
    processed++;
    for (const nei of graph[node]) {
      inDegree[nei]--;
      if (inDegree[nei] === 0) queue.push(nei);
    }
  }
  return processed === numCourses;
}

Tradeoff: Iterative — no stack overflow risk. The processed count check is the cleanest cycle-detection signal: if any cycle exists, those nodes never reach in-degree 0 and are never processed.

ServiceNow-specific tips

ServiceNow interviewers strongly prefer the Kahn's BFS approach because it mirrors how their workflow engine schedules tasks: activities with no pending dependencies run first, and a workflow that never completes (cycle) is detected immediately. Explicitly map courses → workflow activities in your explanation for maximum contextual signal.

Common mistakes

Building the graph in the wrong direction — [a, b] means b is a prerequisite for a, so the edge is b -> a.
In Kahn's algorithm, failing to check `processed === numCourses` at the end — this is the only reliable cycle signal.
In DFS coloring, not resetting state[node] to 2 after all neighbors are fully explored — causes correct nodes to be flagged as cyclic.

Follow-up questions

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

Course Schedule II: return the actual topological order (LC 210).
Detect cycle in an undirected graph (union-find or DFS parent tracking).
Alien dictionary: derive character order from sorted word list using topological sort (LC 269).

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 is better for this problem?

Both are O(V+E). Kahn's is iterative and easier to reason about for cycle detection (count check). DFS is more naturally extensible to finding the actual cycle. At ServiceNow, Kahn's maps more directly to workflow scheduling, so it tends to score higher contextually.

Why is a cycle a problem for course scheduling?

A cycle means A requires B and B requires A — you can never take either course first. In ServiceNow terms, this is a deadlocked workflow where no task can ever start.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →