Skip to main content

207. Course Schedule

mediumAsked at Elastic

Determine if you can finish all courses given prerequisite dependencies — essentially cycle detection in a directed graph. Elastic interviews this because topological ordering and DAG validation are fundamental to Elasticsearch's pipeline processor chains and ingest node dependency resolution.

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

Source citations

Public interview reports confirming this problem appears in Elastic loops.

  • Glassdoor (2025-12)— Elastic SWE candidates report directed graph and topological sort questions appearing in mid-level coding rounds.
  • Blind (2025-10)— Course Schedule and topological ordering cited in Elastic interview threads as problems testing graph traversal beyond simple BFS/DFS.

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. No cycle.

Example 2

Input
numCourses = 2, prerequisites = [[1,0],[0,1]]
Output
false

Explanation: Course 0 requires course 1 and course 1 requires course 0 — a cycle, so impossible.

Approaches

1. DFS — cycle detection with 3-color marking

Build an adjacency list. DFS from each unvisited node. Use three states: unvisited (0), in-progress (1), done (2). If you reach a node in-progress, you found a cycle.

Time
O(V + E)
Space
O(V + E)
function canFinish(numCourses, prerequisites) {
  const adj = Array.from({ length: numCourses }, () => []);
  for (const [a, b] of prerequisites) adj[b].push(a);
  const state = new Array(numCourses).fill(0); // 0=unvisited, 1=in-progress, 2=done
  function dfs(node) {
    if (state[node] === 1) return false; // cycle
    if (state[node] === 2) return true;  // already processed
    state[node] = 1; // mark in-progress
    for (const neighbor of adj[node]) {
      if (!dfs(neighbor)) return false;
    }
    state[node] = 2; // mark done
    return true;
  }
  for (let i = 0; i < numCourses; i++) {
    if (!dfs(i)) return false;
  }
  return true;
}

Tradeoff: O(V+E) time and space. The 3-color approach is clear and maps directly to Kahn's algorithm thinking.

2. BFS topological sort (Kahn's algorithm)

Compute in-degrees for all nodes. Enqueue nodes with in-degree 0. Process the queue: for each node, decrement neighbors' in-degrees and enqueue those that reach 0. If all nodes are processed, no cycle exists.

Time
O(V + E)
Space
O(V + E)
function canFinish(numCourses, prerequisites) {
  const adj = Array.from({ length: numCourses }, () => []);
  const inDegree = new Array(numCourses).fill(0);
  for (const [a, b] of prerequisites) {
    adj[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 > 0) {
    const node = queue.shift();
    processed++;
    for (const neighbor of adj[node]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }
  return processed === numCourses;
}

Tradeoff: Iterative — no recursion stack risk. Kahn's algorithm also directly produces the topological order, which is needed for Course Schedule II (LC 210).

Elastic-specific tips

Mention both DFS and Kahn's approaches, and note that Kahn's produces the topological order as a bonus — useful for Course Schedule II which Elastic often asks as the immediate follow-up. Connect to Elastic's ingest pipelines: 'Elasticsearch ingest processors form a DAG — Kahn's algorithm validates the pipeline configuration at startup and determines processor execution order.'

Common mistakes

  • Only using a 2-state visited array — visited=true cannot distinguish a node in the current DFS path (potential cycle) from a fully-processed node (safe).
  • Forgetting to build the adjacency list before DFS — iterating prerequisites inline is error-prone.
  • Returning false when processing a 'done' node — done means it was already validated, so return true.
  • Not iterating all nodes in the outer loop — disconnected graph components will be missed.

Follow-up questions

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

  • Course Schedule II (LC 210) — return the actual topological order, or an empty array if impossible.
  • Alien Dictionary (LC 269) — derive topological order from a dictionary of alien words.
  • How would you detect a cycle in a distributed task dependency graph across multiple services?

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 instead of two?

Two states (visited/unvisited) cannot distinguish 'currently on the DFS path' from 'fully processed'. A back edge to a gray (in-progress) node indicates a cycle; a back edge to a black (done) node is safe.

Why does Kahn's algorithm detect cycles?

Nodes in a cycle never have in-degree 0 (each depends on another node in the cycle), so they are never enqueued. If processed < numCourses at the end, cycle nodes were skipped.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →