Skip to main content

15. Course Schedule

mediumAsked at Asana

Determine whether a set of courses with prerequisites can all be completed — Asana uses this exact graph-cycle-detection pattern when validating that task dependency graphs in a project remain free of circular blockers.

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

Problem

There are numCourses courses labeled 0 through numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] means you must take course bi before 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
  • 0 <= ai, bi < numCourses
  • All prerequisite pairs are unique

Examples

Example 1

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

Explanation: Take course 0 first, then course 1.

Example 2

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

Explanation: Course 0 requires course 1 and vice-versa — a cycle.

Approaches

1. Brute force DFS with visited set

For each node, run DFS tracking a recursion-stack set to detect back edges. Redundant work across nodes.

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 visited = new Array(numCourses).fill(0); // 0=unvisited,1=visiting,2=done

  function hasCycle(node) {
    if (visited[node] === 1) return true;
    if (visited[node] === 2) return false;
    visited[node] = 1;
    for (const neighbor of adj[node]) {
      if (hasCycle(neighbor)) return true;
    }
    visited[node] = 2;
    return false;
  }

  for (let i = 0; i < numCourses; i++) {
    if (hasCycle(i)) return false;
  }
  return true;
}

Tradeoff:

2. Kahn's algorithm (topological sort / BFS)

Build in-degree counts. Enqueue nodes with in-degree 0 and peel them off, decrementing neighbors. 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:

Asana-specific tips

Asana cares deeply about how you model dependencies — think of prerequisites as task blockers in a project timeline. Interviewers want you to name the pattern (cycle detection in a directed graph), choose between DFS color-marking and Kahn's BFS, and articulate why Kahn's is often friendlier in production systems where you can stream nodes without recursion depth concerns.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →