Skip to main content

78. Course Schedule

mediumAsked at Datadog

Determine if you can finish all courses given prerequisite pairs — equivalent to detecting a cycle in a directed graph. Datadog asks this because their dashboard-dependency graph and metric-rollup DAG must remain acyclic.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — dependency-graph analog.
  • Blind (2025-11)— Recurring at Datadog.

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 3-color

Walk graph; mark visiting/visited; cycle = visiting node re-encountered.

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[a].push(b);
  const state = new Array(n).fill(0); // 0 unvisited, 1 visiting, 2 done
  function dfs(u) {
    if (state[u] === 1) return false;
    if (state[u] === 2) return true;
    state[u] = 1;
    for (const v of adj[u]) if (!dfs(v)) return false;
    state[u] = 2;
    return true;
  }
  for (let i = 0; i < n; i++) if (!dfs(i)) return false;
  return true;
}

Tradeoff: Datadog-canonical. The three-color invariant is the same pattern they use to validate dependency DAGs.

2. Kahn's algorithm (BFS topo sort)

Track in-degrees; repeatedly remove zero-in-degree nodes. If we remove all, no cycle.

Time
O(V + E)
Space
O(V + E)
// Build adjacency + inDegree; queue zero-in-degree; pop, decrement neighbors, queue when their in-degree hits 0. If processed == n, no cycle.

Tradeoff: Iterative; also gives topo-sort order for free. Equally accepted.

Datadog-specific tips

Datadog grades on the three-color (or in-degree) framing. They'll follow up with LC 210 'return the order' — show that Kahn's gives the topo-sort directly. Articulate why two colors don't suffice (can't distinguish current-DFS-stack from finished).

Common mistakes

  • Two colors only — can't detect back edge from finished node.
  • Iterating prerequisites instead of building adjacency — O(V*E) per DFS.
  • Forgetting to reset on graceful completion — leaves stale 'visiting' marks.

Follow-up questions

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

  • Course Schedule II (LC 210) — return the topological order.
  • Alien Dictionary (LC 269) — derive order from constraints.
  • Datadog-style: validate metric-rollup DAG is acyclic before deployment.

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 BFS?

Both work and are O(V + E). DFS is more natural for cycle detection; BFS (Kahn) is more natural for topo order.

Why three colors?

'Visiting' means currently in DFS stack — a back edge to a visiting node is a cycle. 'Visited' means fully explored — re-encountering it is just a cross/forward edge, not a cycle.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →