How do you approach Parallel Courses (Minimum Semesters)?

This is Kahn's algorithm processed in LEVELS rather than one node at a time.

What is the time complexity of Parallel Courses (Minimum Semesters)?

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

What are common mistakes on Parallel Courses (Minimum Semesters)?

Not detecting the cycle. If fewer nodes come out than went in there is no valid ordering, and that is usually the real question. Building the edges the wrong way round - prerequisite pairs are the classic reversal. Seeding the queue with every node instead of only those with zero indegree.

gitGood.dev

← Back to problems

Parallel Courses (Minimum Semesters)

MediumAlgorithms

Description

You are given `n` courses labelled `1` to `n` and a list of `relations` where `relations[i] = [prev, next]` means `prev` must be taken before `next`. In one semester you may take **any number of courses at once**, as long as every prerequisite was taken in an earlier semester. Return the minimum number of semesters needed to take all courses, or `-1` if it is impossible.

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

Example 3

Input: n = 5, relations = [[1,2],[2,3],[3,4],[4,5]]

Output: 5

Constraints

- 1 <= n <= 5000 - 0 <= relations.length <= 5000 - Courses are numbered from 1 to n (not 0) - Return -1 when the prerequisites form a cycle.

Parallel Courses (Minimum Semesters): approach, complexity and pitfalls

A medium topological sort problem, graded against 6 test cases (3 of them hidden).

The pattern: Topological Sort

Ordering a directed acyclic graph so every dependency comes first.

Reach for it when you see: Prerequisites, build order, task scheduling, or "can this be completed?"

More Topological Sortproblems →

If you are stuck

Show the 3-step hint ladder

This is Kahn's algorithm processed in LEVELS rather than one node at a time.
Each round, take every course currently at indegree 0 as one semester, then relax all of their edges together.
Count the rounds, not the courses. If you finish fewer than n courses, there is a cycle - return -1. Courses are 1-indexed, so size your arrays n + 1.

The optimal approach

Show the approach: Level-order topological sort

Because a semester can hold unlimited courses, the answer is the number of levels in the dependency graph - equivalently the length of its longest prerequisite chain.

Run Kahn's algorithm, but process a whole frontier at a time: every course currently at indegree 0 is takeable this semester, so consume them all, relax their outgoing edges, and collect whatever reaches indegree 0 as the next semester's frontier. Increment a counter once per round.

This is exactly BFS level-order traversal applied to a DAG, and it is why the answer equals the longest chain: a course cannot appear before every prerequisite has been consumed in an earlier round.

Two traps. First, count rounds, not courses - a natural but wrong instinct is to increment inside the inner loop. Second, courses are numbered 1 to n, not 0 to n-1, so arrays need `n + 1` slots and the initial scan runs from 1; an off-by-one here silently reports a phantom course at index 0 that never becomes available.

As with Kahn generally, a cycle shows up as courses that never reach indegree 0, so compare the total consumed against `n`.

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

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.

Common Topological Sort mistakes

These apply to the pattern as a whole, not just this problem.

Not detecting the cycle. If fewer nodes come out than went in there is no valid ordering, and that is usually the real question.
Building the edges the wrong way round - prerequisite pairs are the classic reversal.
Seeding the queue with every node instead of only those with zero indegree.