23. Course Schedule

mediumAsked at Tripadvisor

Detect whether a dependency graph contains a cycle — Tripadvisor uses this topological-sort pattern to validate that itinerary leg dependencies (visa requirements, connection airports) form a feasible travel plan with no circular conflicts.

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

Problem

There are numCourses courses labeled 0 to numCourses-1. You are given an array prerequisites where prerequisites[i] = [a, b] means you must take course b before course a. Return true if you can finish all courses, false if there is a circular dependency.

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 first, then course 1.

Example 2

Input

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

Output

false

Explanation: Course 0 depends on 1 and course 1 depends on 0 — circular dependency.

Approaches

1. DFS cycle detection with 3-color marking

Mark nodes as unvisited (0), in-progress (1), or done (2). If DFS reaches an in-progress node, a cycle exists.

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=visiting,2=done
  function dfs(node) {
    if (state[node] === 1) return false; // cycle
    if (state[node] === 2) return true;  // already processed
    state[node] = 1;
    for (const neighbor of adj[node]) {
      if (!dfs(neighbor)) return false;
    }
    state[node] = 2;
    return true;
  }
  for (let i = 0; i < numCourses; i++) {
    if (!dfs(i)) return false;
  }
  return true;
}

Tradeoff:

2. BFS topological sort (Kahn's algorithm)

Compute in-degrees; BFS from zero-in-degree nodes, decrementing neighbors. If all nodes are processed, no cycle exists.

Time: O(V+E)
Space: O(V+E)

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

Tradeoff:

Tripadvisor-specific tips

Tripadvisor graders love this problem because dependency validation maps directly to itinerary feasibility checks — can a traveler complete leg B before leg A given visa and connection constraints? Interviewers want you to name the algorithm (Kahn's BFS or DFS 3-color) rather than re-deriving it. Note that Kahn's BFS is generally preferred in production for large graphs because it avoids call-stack depth limits and also naturally produces the processing order as a bonus.

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 Tripadvisor interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →