Parallel Courses III — Solution in Python, Java & C++
Parallel Courses III solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Parallel Courses III is a hard coding problem on arrays, dynamic programming and graph, asked in Amazon, Google and Two Sigma interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Graph, Topological Sort
- Asked at: Amazon, Google, Two Sigma
- 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
A CodeKairo track has n courses labelled 1 to n. Each relations[j] = [prevCourse, nextCourse] says prevCourse must be finished before nextCourse can start. Course i takes time[i - 1] months.
You may start any course as soon as all its prerequisites are finished, and you may take any number of courses at the same time.
Return the minimum number of months needed to finish every course. The prerequisites are guaranteed to form a directed acyclic graph, so finishing is always possible.
Example 1
Input: n = 4, relations = [[1,2],[1,3],[2,4],[3,4]], time = [2,5,3,1]
Output: 8
Explanation: Course 1 ends at month 2, course 2 at 7, course 3 at 5, so course 4 starts at 7 and ends at 8.
Example 2
Input: n = 3, relations = [], time = [4,9,2]
Output: 9
Explanation: Everything runs in parallel; the longest course decides.
Example 3
Input: n = 5, relations = [[2,1],[3,1],[4,3]], time = [1,6,2,7,3]
Output: 10
Constraints
1 <= n <= 5 * 10^40 <= relations.length <= min(n * (n - 1) / 2, 5 * 10^4)relations[j].length == 21 <= prevCourse, nextCourse <= nprevCourse != nextCourseall pairs [prevCourse, nextCourse] are uniquetime.length == n1 <= time[i] <= 10^4the relations form a directed acyclic graph
Hints for Parallel Courses III
Hint 1
A course can finish no earlier than its own duration plus the latest finish time among its prerequisites.
Hint 2
Compute finish times in an order where every prerequisite is handled before the courses that depend on it.
Hint 3
Kahn's topological sort gives that order: when a course is popped, push its finish time forward to each dependent course as that course's earliest start. The answer is the largest finish time.
How to solve Parallel Courses III
With unlimited parallelism the schedule is the critical path of the DAG: finish(v) = time(v) + max(finish(p)) over prerequisites p, computed in topological order.
Approach
- Build adjacency lists and in-degrees from
relations; letstart[v] = 0for all courses. - Queue every course with in-degree 0.
- Pop
u; its finish time isstart[u] + time[u]. For each dependentv, setstart[v] = max(start[v], finish(u)), decrement its in-degree and queue it at 0. - Return the largest finish time seen.
Why it works
When a course is popped, all its prerequisites were popped before it, so start[u] already equals the latest finish among them — the earliest moment it may begin. Starting every course at that moment is optimal since nothing is gained by waiting, and the whole program ends when the last course does.
Complexity
- Time —
O(n + m) - Space —
O(n + m)
Pitfalls
- Courses are 1-indexed in
relationsbuttimeis 0-indexed. - The answer is the maximum finish over all courses, not the finish of the last course popped.
- Courses with no relations at all still count — they run from month 0.
Reference solution
Python
from typing import List
from collections import deque
def minimumTime(n: int, relations: List[List[int]], time: List[int]) -> int:
adj = [[] for _ in range(n)]
indeg = [0] * n
for a, b in relations:
adj[a - 1].append(b - 1)
indeg[b - 1] += 1
start = [0] * n
q = deque(i for i in range(n) if indeg[i] == 0)
best = 0
while q:
u = q.popleft()
finish = start[u] + time[u]
if finish > best:
best = finish
for v in adj[u]:
if finish > start[v]:
start[v] = finish
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return bestJava
public static int minimumTime(int n, int[][] relations, int[] time) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
int[] indeg = new int[n];
for (int[] r : relations) { adj.get(r[0] - 1).add(r[1] - 1); indeg[r[1] - 1]++; }
int[] start = new int[n];
int[] queue = new int[n];
int head = 0, tail = 0;
for (int i = 0; i < n; i++) if (indeg[i] == 0) queue[tail++] = i;
int best = 0;
while (head < tail) {
int u = queue[head++];
int finish = start[u] + time[u];
best = Math.max(best, finish);
for (int v : adj.get(u)) {
if (finish > start[v]) start[v] = finish;
if (--indeg[v] == 0) queue[tail++] = v;
}
}
return best;
}C++
int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
vector<vector<int>> adj(n);
vector<int> indeg(n, 0), start(n, 0), queue;
for (auto& r : relations) { adj[r[0] - 1].push_back(r[1] - 1); indeg[r[1] - 1]++; }
for (int i = 0; i < n; i++) if (indeg[i] == 0) queue.push_back(i);
int best = 0;
for (size_t h = 0; h < queue.size(); h++) {
int u = queue[h];
int finish = start[u] + time[u];
best = max(best, finish);
for (int v : adj[u]) {
if (finish > start[v]) start[v] = finish;
if (--indeg[v] == 0) queue.push_back(v);
}
}
return best;
}JavaScript
var minimumTime = function(n, relations, time) {
var adj = [], indeg = [], start = [];
for (var i = 0; i < n; i++) { adj.push([]); indeg.push(0); start.push(0); }
for (var r = 0; r < relations.length; r++) {
adj[relations[r][0] - 1].push(relations[r][1] - 1);
indeg[relations[r][1] - 1]++;
}
var queue = [];
for (var s = 0; s < n; s++) if (indeg[s] === 0) queue.push(s);
var best = 0;
for (var h = 0; h < queue.length; h++) {
var u = queue[h];
var finish = start[u] + time[u];
if (finish > best) best = finish;
for (var j = 0; j < adj[u].length; j++) {
var v = adj[u][j];
if (finish > start[v]) start[v] = finish;
if (--indeg[v] === 0) queue.push(v);
}
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming