Parallel Courses

Medium Graphs Topological Sort Original on LeetCode

Reported atNetflixSnowflake

Parallel Courses is a medium graphs problem solved with the topological sort pattern. The best approach, optimal (kahn's algorithm, level by level), runs in O(n + m) time and O(n + m) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (simulate semester by semester) up.

Problem

There are n courses labelled 1 to n. Each entry relations[i] = [prev, next] says that course prev must be completed in an earlier semester than course next.

In one semester you may take any number of courses, as long as all of their prerequisites were finished in previous semesters. Return the minimum number of semesters needed to complete every course, or -1 if it is impossible because some prerequisites form a cycle.

Examples

Example 1

Input
n = 4, relations = [[1, 3], [2, 3], [3, 4]]
Output
3
Why
Semester 1: courses 1 and 2. Semester 2: course 3. Semester 3: course 4.

Example 2

Input
n = 5, relations = [[1, 2], [2, 4], [4, 1], [3, 5]]
Output
-1
Why
Courses 1, 2 and 4 wait on each other in a loop, so none of them can ever be started.

Example 3

Input
n = 3, relations = []
Output
1
Why
With no prerequisites, all three courses fit in the first semester.

Constraints

  • 1 <= n <= 5000
  • 0 <= relations.length <= 5000
  • relations[i] = [prev, next] with 1 <= prev, next <= n and prev != next
  • All pairs in relations are distinct.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (simulate semester by semester)O(n · (n + m))O(n)
Optimal (Kahn's algorithm, level by level)O(n + m)O(n + m)

1Brute force (simulate semester by semester)

TimeO(n · (n + m))Up to n semesters, each scanning all courses and all m relations.
SpaceO(n)A few arrays of size n.

Repeat: look at every course not yet taken and check, by scanning all relations, whether all its prerequisites were finished in an earlier semester. Take all such courses at once. If a semester adds nothing while courses remain, the remaining ones are stuck in a cycle.

  1. Keep a done array and a counter of finished courses.
  2. Each semester, mark a course ready if no relation [p, c] has p unfinished (judged by the state at the start of the semester).
  3. If no course is ready, return -1; otherwise mark them done and add one semester.
  4. Stop when all n courses are done.
class Solution {
    public int minimumSemesters(int n, int[][] relations) {
        boolean[] done = new boolean[n + 1];
        int finished = 0, semesters = 0;
        while (finished < n) {
            boolean[] blocked = new boolean[n + 1];
            for (int[] r : relations) {
                if (!done[r[0]]) blocked[r[1]] = true;
            }
            List<Integer> ready = new ArrayList<>();
            for (int c = 1; c <= n; c++) {
                if (!done[c] && !blocked[c]) ready.add(c);
            }
            if (ready.isEmpty()) return -1;
            for (int c : ready) done[c] = true;
            finished += ready.size();
            semesters++;
        }
        return semesters;
    }
}

2Optimal (Kahn's algorithm, level by level)

TimeO(n + m)Every course is dequeued once and every relation is relaxed once.
SpaceO(n + m)Adjacency lists, in-degree array and the queue.

Build the graph and the in-degree of every course. Start a queue with all in-degree-zero courses; that is semester 1. Pop a whole level at a time, lower the in-degree of each successor, and push successors that reach zero into the next level. Count the levels and the courses taken; if fewer than n courses were taken, a cycle blocked the rest.

  1. Build adjacency lists prev -> next and the in-degree array.
  2. Queue every course with in-degree 0.
  3. While the queue is not empty: semesters++, and process exactly the current queue size, decrementing in-degrees of successors and enqueuing those that hit 0.
  4. Return semesters if every course was dequeued, otherwise -1.
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 c = 1; c <= n; c++) if (indeg[c] == 0) q.add(c);
        int taken = 0, semesters = 0;
        while (!q.isEmpty()) {
            semesters++;
            for (int size = q.size(); size > 0; size--) {
                int c = q.poll();
                taken++;
                for (int nx : adj.get(c)) {
                    if (--indeg[nx] == 0) q.add(nx);
                }
            }
        }
        return taken == n ? semesters : -1;
    }
}

Edge cases to test

  • No relations at all: the answer is 1
  • A single long chain 1 -> 2 -> ... -> n: the answer is n
  • A cycle in one part of the graph while other parts are fine: still -1
  • A course with many prerequisites finishing on different semesters: it waits for the latest one

Hints

Hint 1

Draw an edge prev -> next. In each semester you can take every course whose prerequisites are all done.

Hint 2

Count, for every course, how many prerequisites are still missing (its in-degree). The courses with zero form the first semester.

Hint 3

Process the graph level by level like a BFS (Kahn's algorithm). The number of levels is the answer; if some course is never reached, there is a cycle.

FAQ

What is the best time complexity for Parallel Courses?

Optimal (Kahn's algorithm, level by level) runs in O(n + m) time and O(n + m) extra space. Every course is dequeued once and every relation is relaxed once.

Which pattern does Parallel Courses use?

It is a graphs problem that uses the topological sort pattern. Other problems with the same pattern: Topological sort using BFS, Course Schedule, Course Schedule II.

Is there a brute force solution for Parallel Courses?

Yes. Brute force (simulate semester by semester) takes O(n · (n + m)) time and O(n) space. Repeat: look at every course not yet taken and check, by scanning all relations, whether all its prerequisites were finished in an earlier semester.

Which edge cases should I test for Parallel Courses?

No relations at all: the answer is 1; A single long chain 1 - 2 - ... - n: the answer is n; A cycle in one part of the graph while other parts are fine: still -1; A course with many prerequisites finishing on different semesters: it waits for the latest one.