Command Palette

Search for a command to run...

Hectal
Problem 24.3 · Topological SortMedium

Parallel Courses

PatternTopological Sort

What it teaches: Kahn's algorithm level by level: the number of levels is the minimum number of rounds.

Practise it on judges as “Parallel Courses”.

The problem

Courses are 1..n; relations[i] = [prev, next] means prev before next. Each semester you can take any number of courses whose prerequisites are done. Return the minimum number of semesters, or −1 if impossible.

Example 1

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

Constraints

  • 1 ≤ n ≤ 5000

Pattern clues in the wording

  • → Unlimited parallelism
  • → Minimum number of rounds

These clues point to Topological Sort: Order the nodes of a directed graph so every edge goes from earlier to later, by repeatedly taking nodes with no remaining prerequisites.

Stuck? Take one hint at a time

Solution.java · starter
import java.util.*;

class Solution {
    public int minimumSemesters(int n, int[][] relations) {
        return -1;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
n = 3
relations = [[1,3],[2,3]]
2
2
n = 3
relations = [[1,2],[2,3],[3,1]]
-1

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Level-order Kahn's · O(n + E)
1

Level-order Kahn's

Time O(n + E) Space O(n + E)

Queue in-degree-0 courses. Each pass over the current queue size is a semester. Count courses taken; fewer than n means a cycle.

Approach 1
import java.util.*;

class Solution {
    public 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]]++; }
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) if (indeg[i] == 0) q.offer(i);
        int semesters = 0, taken = 0;
        while (!q.isEmpty()) {
            semesters++;
            for (int size = q.size(); size > 0; size--) {
                int u = q.poll();
                taken++;
                for (int v : adj.get(u)) if (--indeg[v] == 0) q.offer(v);
            }
        }
        return taken == n ? semesters : -1;
    }
}

Verdict: BFS levels on a DAG.

Before you submit

Edge cases and common mistakes

Test these inputs

  • No relations (1 semester)
  • A cycle (−1)

Mistakes people make

  • Counting semesters per course instead of per level.

Interview

Follow-up questions

What if at most k courses fit in one semester (Parallel Courses II)?