26. Course Schedule

mediumAsked at Instacart

Detect whether a set of prerequisite dependencies contains a cycle — Instacart uses topological-sort cycle detection when validating that recipe ingredient substitution chains don't loop back on themselves.

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

Problem

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

Constraints

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= a_i, b_i < numCourses
All pairs [a_i, b_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: 0 requires 1 and 1 requires 0 — a cycle.

Approaches

1. DFS cycle detection (coloring)

Mark each node as unvisited (0), visiting (1), or visited (2). If we reach a node marked visiting during DFS, a back-edge (cycle) exists.

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

function canFinish(numCourses, prerequisites) {
  const graph = Array.from({ length: numCourses }, () => []);
  for (const [a, b] of prerequisites) graph[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 cleared
    state[node] = 1;
    for (const nei of graph[node]) {
      if (!dfs(nei)) 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, enqueue nodes with in-degree 0, and process in BFS order. If we can process all nodes, there is no cycle.

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

function canFinish(numCourses, prerequisites) {
  const inDegree = new Array(numCourses).fill(0);
  const graph = Array.from({ length: numCourses }, () => []);

  for (const [a, b] of prerequisites) {
    graph[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 nei of graph[node]) {
      inDegree[nei]--;
      if (inDegree[nei] === 0) queue.push(nei);
    }
  }

  return processed === numCourses;
}

Tradeoff:

Instacart-specific tips

Instacart's catalog uses dependency chains for ingredient substitutions and recipe ordering. Both DFS-coloring and Kahn's BFS are acceptable; interviewers prefer BFS (Kahn's) because it naturally produces the topological order if needed for follow-ups, and it avoids recursion-depth risk on large dependency graphs.

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

Practice these live with InterviewChamp.AI →