HardArrayDynamic ProgrammingGraphTopological SortUpdated Sep 2026

2050. Parallel Courses III

Asked at Snowflake

Difficulty

Hard

Time

O(n + e)

Space

O(n + e)

Pattern

Array

Companies

1

Problem

You are given n courses, numbered 1 to n. Each course takes a known number of months to finish: time[i] is the duration of course i+1. You are also given relations, where each pair [a, b] means course a must be fully finished before course b can begin.

You may start any course as soon as all of its prerequisites are done, and you may run as many courses at the same time as you like. There is no limit on how many run in parallel.

Return the minimum number of months needed to finish every course. The input graph is guaranteed to be a DAG (directed acyclic graph), so a valid order always exists.

Courses 1 and 2 run in parallel, then 3

course 1: 0 → 3course 2: 0 → 2course 3: 3 → 8Courses 1 and 2 overlap; course 3 waits for the slowerone.time325012Durations of courses 1, 2 and 3; the answer is 3 + 5 =8.
Course 3 cannot start until both course 1 (3 months) and course 2 (2 months) are done, so it starts at month 3.

Constraints

  • ●1 <= n <= 5 * 10^4
  • ●0 <= relations.length <= min(n * (n - 1) / 2, 5 * 10^4)
  • ●relations[j].length == 2
  • ●1 <= prevCoursej, nextCoursej <= n
  • ●prevCoursej != nextCoursej
  • ●All pairs [prevCoursej, nextCoursej] are unique
  • ●time.length == n
  • ●1 <= time[i] <= 10^4

Examples

Example 1
Inputn = 3, relations = [[1,3],[2,3]], time = [3,2,5]
Output8
WhyCourses 1 and 2 have no prerequisites, so both start at month 0. Course 1 ends at month 3 and course 2 ends at month 2. Course 3 needs both of them, so it can only start at month max(3, 2) = 3. It runs for 5 months, ending at month 8. That is the last course to finish, so the answer is 8.
Example 2
Inputn = 5, relations = [[1,5],[2,5],[3,5],[3,4],[4,5]], time = [1,2,3,4,5]
Output12
WhyCourses 1, 2 and 3 start at month 0 and end at months 1, 2 and 3. Course 4 waits for course 3, so it starts at month 3 and ends at month 7. Course 5 waits for courses 1, 2, 3 and 4, so it starts at month max(1, 2, 3, 7) = 7 and ends at month 7 + 5 = 12. Nothing finishes later, so the answer is 12.

Asked At

1 companies
CompanyDifficulty
SnowflakeHardView all Snowflake questions →

How to Think About It

1

Because courses can run in parallel, a course starts as soon as its last prerequisite finishes. The overall finish time is the latest finish of any course.

2

Key insight: finish[v] = time[v] + max(finish[u] for each prerequisite u). That is DP over a DAG in topological order — the critical-path method from project scheduling.

3

Kahn's algorithm: start with all courses that have no prerequisites (finish = time). When you pop u, update each dependent v with start[v] = max(start[v], finish[u]) and decrement its in-degree; enqueue it at zero.

4

The answer is max(finish).

5

Walkthrough: n = 3, relations 1->3, 2->3, times [3,2,5]: course 3 starts at max(3, 2) = 3 and finishes at 8.

Optimal Approach

Step 1: Build adjacency lists and in-degrees (courses are 1-indexed).
Step 2: start = [0] * n; enqueue courses with in-degree 0.
Step 3: Pop u: finish = start[u] + time[u]; for each v in adj[u]: start[v] = max(start[v], finish); decrement in-degree; enqueue at 0.
Step 4: Return max(start[i] + time[i]).

Time: O(n + e). Space: O(n + e).

Topological order with start times

indegree 0: courses 1, 2pop 1 → start[3] = 3pop 2 → start[3] = max(3, 2) = 3pop 3 → finish = 3 + 5 = 8Kahn's algorithm pops courses only when allprerequisites are done.start003012start[3]=3After both prerequisites finish, course 3 has starttime 3.start[v] = max(start[v], finish[u])finish[u] = start[u] + time[u]answer = max(finish)
Each course starts at the latest finish time among its prerequisites, then adds its own duration.
ComplexityTime O(n + e)Space O(n + e)Each course and each prerequisite edge is processed once by the topological sort; the space holds the adjacency list, in-degrees and start times.

What Trips People Up in Real Interviews

1

Summing all durations. Courses run in parallel, so only the critical path matters.

2

Using BFS levels (like Parallel Courses I) and adding one duration per level — levels ignore that courses in the same level have different durations.

3

Off-by-one on 1-indexed course numbers.

4

Returning the finish time of the last course dequeued rather than the maximum over all courses.

Solution Code

O(n + e) time
from collections import deque

def minimumTime(n, relations, time):
    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)
    while q:
        u = q.popleft()
        done = start[u] + time[u]
        for v in adj[u]:
            start[v] = max(start[v], done)
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return max(start[i] + time[i] for i in range(n))

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Parallel Courses III problem?

Parallel Courses III gives you courses with durations and prerequisite relations, and lets you take any number of courses at the same time. What is the minimum time to finish them all? It is the longest (critical) path through a DAG, computed with a topological sort.

How do you solve Parallel Courses III?

The optimal approach runs in O(n + e) time and O(n + e) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Parallel Courses III?

Parallel Courses III is asked at Snowflake. It is a hard difficulty problem.

What are common mistakes on Parallel Courses III?
  • Summing all durations. Courses run in parallel, so only the critical path matters.
  • Using BFS levels (like Parallel Courses I) and adding one duration per level — levels ignore that courses in the same level have different durations.
  • Off-by-one on 1-indexed course numbers.
  • Returning the finish time of the last course dequeued rather than the maximum over all courses.