Skip to main content

71. Course Schedule

mediumAsked at Workday

Determine if you can finish all courses given prerequisite dependencies. Workday uses this for cycle-detection in workflow DAGs — same shape as validating that an approval-chain definition doesn't loop back on itself.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025-Q4)— Workday SDE2 onsite — workflow-team direct analogy.
  • Blind (2026)— Workday Pleasanton workflow-engine question.

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

Each node: 0=unvisited, 1=in-progress, 2=done. Cycle = revisit a 1-marked node.

Time
O(V + E)
Space
O(V + E)
// DFS with WHITE/GRAY/BLACK states

Tradeoff: Works. Slightly more code than Kahn's algorithm.

2. Kahn's algorithm (BFS topo sort)

Compute in-degrees. Repeatedly remove zero-in-degree nodes. If all nodes removed, no cycle.

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 [course, pre] of prerequisites) {
    graph[pre].push(course);
    inDegree[course]++;
  }
  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 next of graph[node]) {
      inDegree[next]--;
      if (inDegree[next] === 0) queue.push(next);
    }
  }
  return processed === numCourses;
}

Tradeoff: Kahn's BFS naturally exits when stuck — if cycle, leftover nodes have positive in-degree. Counter at the end is the validity check.

Workday-specific tips

Workday wants Kahn's because it directly mirrors workflow-engine semantics: 'process nodes whose dependencies are satisfied'. State this analogy. The 'processed == numCourses' check is the cycle detection.

Common mistakes

  • Reversing the edge direction — should be from prereq to course.
  • Forgetting the in-degree decrement when removing a node.
  • Returning queue.length instead of processed count comparison.

Follow-up questions

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

  • Course Schedule II (LC 210) — return the actual order.
  • Alien Dictionary (LC 269) — topo sort on chars.
  • Detect cycle in directed graph (general).

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?

Both are O(V+E). Kahn's is more natural for 'can I process this?' questions. DFS is shorter for raw cycle detection.

Why processed count?

If any node is in a cycle, its in-degree never drops to zero — it never enters the queue. The unprocessed count = nodes stuck in cycles.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →