Parallel Courses

Medium
944.

Parallel Courses

Parallel Courses is a medium coding problem on breadth-first search, graph and topological sort, asked in Amazon, Google and Adobe interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} relations
 * @return {number}
 */
var minimumSemesters = function(n, relations) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Parallel Courses — Solution in Python, Java & C++

Parallel Courses solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Parallel Courses is a medium coding problem on breadth-first search, graph and topological sort, asked in Amazon, Google and Adobe interviews.

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.

Hints for Parallel Courses

  1. Hint 1

    Because a semester holds any number of courses, take everything whose prerequisites are done.

  2. Hint 2

    That is a topological sort processed one whole layer at a time.

  3. Hint 3

    If some course is never freed, the prerequisites contain a cycle.

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

  1. Count in-degrees and queue every course with none.
  2. Each round, take the entire current queue as one semester and decrement its successors' in-degrees.
  3. Courses reaching in-degree 0 form the next round's queue.
  4. 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

Java

public static int minimumSemesters(int n, int[][] relations) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
    int[] indeg = new int[n + 1];
    for (int[] r : relations) {
        adj.get(r[0]).add(r[1]);
        indeg[r[1]]++;
    }
    List<Integer> q = new ArrayList<>();
    for (int i = 1; i <= n; i++) if (indeg[i] == 0) q.add(i);
    int taken = 0, sem = 0;
    while (!q.isEmpty()) {
        sem++;
        List<Integer> nq = new ArrayList<>();
        for (int u : q) {
            taken++;
            for (int v : adj.get(u)) {
                if (--indeg[v] == 0) nq.add(v);
            }
        }
        q = nq;
    }
    return taken == n ? sem : -1;
}

C++

int minimumSemesters(int n, vector<vector<int>>& relations) {
    vector<vector<int>> adj(n + 1);
    vector<int> indeg(n + 1, 0);
    for (auto& r : relations) {
        adj[r[0]].push_back(r[1]);
        indeg[r[1]]++;
    }
    vector<int> q;
    for (int i = 1; i <= n; i++) if (indeg[i] == 0) q.push_back(i);
    int taken = 0, sem = 0;
    while (!q.empty()) {
        sem++;
        vector<int> nq;
        for (int u : q) {
            taken++;
            for (int v : adj[u]) {
                if (--indeg[v] == 0) nq.push_back(v);
            }
        }
        q = nq;
    }
    return taken == n ? sem : -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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 156 breadth-first search problems · the whole catalogue

Learn the technique: Breadth-First Search (BFS) · Graph Data Structure