Skip to main content

24. Parallel Courses

mediumAsked at CircleCI

Determine the minimum number of semesters to complete all courses in parallel, which maps exactly to CircleCI's minimum pipeline stage count with parallel job execution.

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

Problem

Given n courses and a list of relations [prevCourse, nextCourse], return the minimum number of semesters to finish all courses. In each semester you can take any number of courses without prerequisites met. Return -1 if impossible.

Constraints

  • 1 <= n <= 5000
  • 1 <= relations.length <= 5000
  • All relations are distinct

Examples

Example 1

Input
n = 3, relations = [[1,3],[2,3]]
Output
2

Example 2

Input
n = 3, relations = [[1,2],[2,3],[3,1]]
Output
-1

Approaches

1. BFS layer-by-layer (Kahn's)

Process all zero-in-degree nodes each round (one semester), decrement neighbor in-degrees, enqueue newly free nodes; count rounds.

Time
O(V+E)
Space
O(V+E)
function minimumSemesters(n, relations) {
  const indegree = new Array(n + 1).fill(0);
  const graph = Array.from({length: n + 1}, () => []);
  for (const [u, v] of relations) { graph[u].push(v); indegree[v]++; }
  let queue = [];
  for (let i = 1; i <= n; i++) if (indegree[i] === 0) queue.push(i);
  let semesters = 0, taken = 0;
  while (queue.length) {
    const next = [];
    for (const u of queue) {
      taken++;
      for (const v of graph[u]) { if (--indegree[v] === 0) next.push(v); }
    }
    queue = next; semesters++;
  }
  return taken === n ? semesters : -1;
}

Tradeoff:

2. DAG longest path (DP)

Compute the longest path in the DAG via DP; each node's value is 1 + max(predecessors). The answer is the max value across all nodes.

Time
O(V+E)
Space
O(V)
function minimumSemesters(n, relations) {
  const indegree = new Array(n + 1).fill(0);
  const graph = Array.from({length: n + 1}, () => []);
  for (const [u, v] of relations) { graph[u].push(v); indegree[v]++; }
  const dp = new Array(n + 1).fill(1);
  const queue = [];
  for (let i = 1; i <= n; i++) if (indegree[i] === 0) queue.push(i);
  let count = 0;
  while (queue.length) {
    const u = queue.shift(); count++;
    for (const v of graph[u]) {
      dp[v] = Math.max(dp[v], dp[u] + 1);
      if (--indegree[v] === 0) queue.push(v);
    }
  }
  return count === n ? Math.max(...dp.slice(1)) : -1;
}

Tradeoff:

CircleCI-specific tips

CircleCI interviewers specifically look for the DAG longest-path insight — the minimum stages equals the critical path length, the same concept used to estimate pipeline duration before any job runs.

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

Practice these live with InterviewChamp.AI →