Parallel Courses — Medium Problem & Solution

There are n courses numbered 1 … n. relations[i] = [prev, next] means course prev must be taken before course next.

Difficulty: Medium
Topics: Breadth-First Search, Graph, Topological Sort
Asked at: Amazon, Google, Adobe
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

There are n courses numbered 1 … n. relations[i] = [prev, next] means course prev must be taken before course next.

In one semester you may take any number of courses, as long as every prerequisite of each was taken in an earlier semester. Return the minimum number of semesters needed to take all n courses, or -1 if that is impossible.

Example 1

Input: n = 3, relations = [[1,3],[2,3]]
Output: 2
Explanation: Take courses 1 and 2 together, then course 3.

Example 2

Input: n = 3, relations = [[1,2],[2,3],[3,1]]
Output: -1
Explanation: The prerequisites form a cycle.

Example 3

Input: n = 4, relations = []
Output: 1
Explanation: Everything can be taken at once.

Constraints

1 <= n <= 5000
1 <= relations.length <= 5000
relations[i].length == 2
1 <= prev, next <= n
prev != next
All the pairs are unique.

How to solve Parallel Courses

Run Kahn's algorithm, but peel a whole layer per round. The number of rounds is the number of semesters; if fewer than n courses are ever taken, a cycle blocks the rest.

Approach

Count in-degrees and queue every course with none.
Each round, take the entire current queue as one semester and decrement its successors' in-degrees.
Courses reaching in-degree 0 form the next round's queue.
Return the round count if all n courses were taken, and -1 otherwise.

Why it works

Taking every available course immediately is optimal because a course can never be a reason to delay another — courses are free and unlimited, so there is no trade-off to weigh. That makes the layered peel a lower bound as well as achievable, and the layer number of a course is the length of its longest prerequisite chain.

Complexity

Time — O(n + m)
Space — O(n + m)

Pitfalls

Courses are numbered from 1; size the arrays accordingly.
A cycle shows as a shortfall in the taken count, not as an error during the sweep.
Peeling one course at a time counts courses, not semesters.

Reference solution

Python

from typing import List

def minimumSemesters(n: int, relations: List[List[int]]) -> int:
    adj = [[] for _ in range(n + 1)]
    indeg = [0] * (n + 1)
    for a, b in relations:
        adj[a].append(b)
        indeg[b] += 1
    q = [i for i in range(1, n + 1) if indeg[i] == 0]
    taken = 0
    sem = 0
    while q:
        sem += 1
        nq = []
        for u in q:
            taken += 1
            for v in adj[u]:
                indeg[v] -= 1
                if indeg[v] == 0:
                    nq.append(v)
        q = nq
    return sem if taken == n else -1

JavaScript

var minimumSemesters = function(n, relations) {
    var i;
    var adj = [], indeg = [];
    for (i = 0; i <= n; i++) { adj.push([]); indeg.push(0); }
    for (i = 0; i < relations.length; i++) {
        adj[relations[i][0]].push(relations[i][1]);
        indeg[relations[i][1]]++;
    }
    var q = [];
    for (i = 1; i <= n; i++) if (indeg[i] === 0) q.push(i);
    var taken = 0, sem = 0;
    while (q.length > 0) {
        sem++;
        var nq = [];
        for (var k = 0; k < q.length; k++) {
            var u = q[k];
            taken++;
            for (var t = 0; t < adj[u].length; t++) {
                var v = adj[u][t];
                indeg[v]--;
                if (indeg[v] === 0) nq.push(v);
            }
        }
        q = nq;
    }
    return taken === n ? sem : -1;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 65 breadth-first search problems · the whole catalogue