Skip to main content
Talentd

Parallel Courses III - Solution & Explanation

HardArrayDynamic ProgrammingGraphTopological Sort27 min readAsked at: Amazon, Microsoft, Snowflake +6
Practice this problem

Problem Statement

You are given an integer n, which indicates that there are n courses labeled from 1 to n. You are also given a 2D integer array relations where relations[j] = [prevCoursej, nextCoursej] denotes that course prevCoursej has to be completed before course nextCoursej (prerequisite relationship). Furthermore, you are given a 0-indexed integer array time where time[i] denotes how many months it takes to complete the (i+1)th course.

You must find the minimum number of months needed to complete all the courses following these rules:

  • You may start taking a course at any time if the prerequisites are met.
  • Any number of courses can be taken at the same time.

Return the minimum number of months needed to complete all the courses.

Note: The test cases are generated such that it is possible to complete every course (i.e., the graph is a directed acyclic graph).

 

Example 1:

Input: n = 3, relations = [[1,3],[2,3]], time = [3,2,5]
Output: 8
Explanation: The figure above represents the given graph and the time required to complete each course. 
We start course 1 and course 2 simultaneously at month 0.
Course 1 takes 3 months and course 2 takes 2 months to complete respectively.
Thus, the earliest time we can start course 3 is at month 3, and the total time required is 3 + 5 = 8 months.

Example 2:

Input: n = 5, relations = [[1,5],[2,5],[3,5],[3,4],[4,5]], time = [1,2,3,4,5]
Output: 12
Explanation: The figure above represents the given graph and the time required to complete each course.
You can start courses 1, 2, and 3 at month 0.
You can complete them after 1, 2, and 3 months respectively.
Course 4 can be taken only after course 3 is completed, i.e., after 3 months. It is completed after 3 + 4 = 7 months.
Course 5 can be taken only after courses 1, 2, 3, and 4 have been completed, i.e., after max(1,2,3,7) = 7 months.
Thus, the minimum time needed to complete all the courses is 7 + 5 = 12 months.

 

Constraints:

  • 1 <= n <= 5 * 104
  • 0 <= relations.length <= min(n * (n - 1) / 2, 5 * 104)
  • relations[j].length == 2
  • 1 <= prevCoursej, nextCoursej <= n
  • prevCoursej != nextCoursej
  • All the pairs [prevCoursej, nextCoursej] are unique.
  • time.length == n
  • 1 <= time[i] <= 104
  • The given graph is a directed acyclic graph.

Approach Overview

Problem Overview: You are given n courses where each course takes a specific amount of time to complete. Some courses depend on others through prerequisite relations. Multiple courses can run in parallel as long as their prerequisites are finished. The task is to compute the minimum time required to complete all courses.

Approach 1: Topological Sort with Dynamic Programming (O(n + m) time, O(n + m) space)

This problem naturally maps to a directed acyclic graph (DAG). Each course is a node, and each prerequisite relation is a directed edge. The key idea is that a course can only start after all prerequisite courses finish, so the completion time becomes the maximum finish time among its prerequisites plus its own duration.

Build an adjacency list and track the in-degree of each node. Run Kahn’s algorithm for topological sort using a queue. Maintain a DP array where dp[i] stores the earliest time course i can finish. Initialize it with the course duration. When processing an edge u → v, update dp[v] = max(dp[v], dp[u] + time[v]). This ensures the longest prerequisite chain determines the start time.

Once all nodes are processed, the answer is the maximum value in the DP array. This approach works because a topological order guarantees that all prerequisites of a course are processed before the course itself. The algorithm runs in linear time relative to nodes and edges, making it ideal for large DAGs commonly seen in scheduling problems on graph structures.

Approach 2: DFS with Memoization (O(n + m) time, O(n + m) space)

An alternative approach computes the longest path in the DAG using depth-first search. Treat each course as a node and recursively calculate the total time required to complete it. The DFS explores all prerequisite chains and returns the maximum time among them plus the current course duration.

Memoization avoids recomputing results. Maintain a cache where memo[i] stores the time required to finish course i including all prerequisites. During DFS, iterate through neighbors in the adjacency list and compute time[i] + max(dfs(next)). If a value already exists in the memo table, reuse it immediately.

This effectively finds the longest path in a DAG, a common pattern in dynamic programming on graphs. The recursion depth corresponds to prerequisite chains, while memoization guarantees each node is evaluated once.

Recommended for interviews: Topological Sort with Dynamic Programming is the approach most interviewers expect. It clearly models dependency resolution and scheduling while staying iterative and efficient. Implementing DFS with memoization also works and demonstrates understanding of longest-path problems in DAGs, but the topological approach tends to be easier to reason about and debug under interview constraints.

Approach 1: Topological Sort with Dynamic Programming

This approach involves topologically sorting the courses based on their prerequisites and then calculating the minimal time to complete each course using dynamic programming.

  • Create a directed graph where each course is a node, and a prerequisite relationship (a,b) is a directed edge from a to b.
  • Perform a topological sort on the courses. This step ensures that all prerequisites of a course are considered before the course itself.
  • Use dynamic programming to calculate the minimum time required to complete each course by iteratively adding its prerequisite's completion time.

This C solution initializes adjacency lists for the graph and an array for in-degrees. The courses are processed based on their prerequisites using a queue (to implement the topological sort). The dp array keeps track of the minimum time to finish each course as the prerequisites are progressively met. The total time to complete all courses becomes the maximum value in the dp array.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + E), where n is the number of courses and E is the number of prerequisite relationships, due to traversing all nodes and edges once.
Space Complexity: O(n + E), needed to store the graph and additional arrays.

Try this approach in the editor →

Approach 2: DFS with Memorization

This approach uses Depth-First Search (DFS) with memorization to efficiently compute the completion time for courses.

  • Model the courses and prerequisites as a directed graph.
  • Utilize DFS to explore courses, where each exploration path calculates the time required as we resolve prerequisites recursively.
  • Utilize memorization to store already computed completion times, avoiding redundant calculations and ensuring optimal performance.

This C implementation makes use of a recursive DFS function to calculate the minimum completion time for each course by traversing through its dependencies. Memorization is utilized to store the time taken to complete each course dp[u], thus optimizing the solution by preventing recalculations.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + E), visiting each node and edge at least once.
Space Complexity: O(n + E), due to storage for graph data and function call stack.

Try this approach in the editor →

Approach 3: Topological Sorting + Dynamic Programming

First, we construct a directed acyclic graph based on the given prerequisite course relationships, perform topological sorting on this graph, and then use dynamic programming to find the minimum time required to complete all courses according to the results of the topological sorting.

We define the following data structures or variables:

  • Adjacency list g stores the directed acyclic graph, and an array indeg stores the in-degree of each node;
  • Queue q stores all nodes with an in-degree of 0;
  • Array f stores the earliest completion time of each node, initially f[i] = 0;
  • Variable ans records the final answer, initially ans = 0;

When q is not empty, take out the head node i in turn, traverse each node j in g[i], update f[j] = max(f[j], f[i] + time[j]), update ans = max(ans, f[j]) at the same time, and reduce the in-degree of j by 1. If the in-degree of j is 0 at this time, add j to the queue q;

Finally, return ans.

The time complexity is O(m + n), and the space complexity is O(m + n). Where m is the length of the array relations.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Topological Sort with Dynamic Programming

Time Complexity: O(n + E), where n is the number of courses and E is the number of prerequisite relationships, due to traversing all nodes and edges once.
Space Complexity: O(n + E), needed to store the graph and additional arrays.

DFS with Memorization

Time Complexity: O(n + E), visiting each node and edge at least once.
Space Complexity: O(n + E), due to storage for graph data and function call stack.

Topological Sorting + Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Topological Sort with Dynamic ProgrammingO(n + m)O(n + m)Best general solution for DAG scheduling problems with prerequisites
DFS with MemoizationO(n + m)O(n + m)Useful when modeling the problem as longest path in a DAG using recursion

Video Solution

Parallel Courses III - Leetcode 2050 - Python • NeetCodeIO • 20,503 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Parallel Courses III easy or hard?
Parallel Courses III is classified as a Hard problem because it combines multiple concepts: graph modeling, topological sorting, and dynamic programming on DAGs. The difficulty comes from recognizing that the task is essentially finding the longest weighted path in a directed acyclic graph.
Parallel Courses III Python/Java solution
Most implementations follow the same structure across languages: build an adjacency list, compute in-degrees, perform topological sort using a queue, and update a DP array for completion times. The logic is identical in Python, Java, C++, C#, and JavaScript with only syntax differences.
How to solve Parallel Courses III in O(n + m)?
Model the courses as a DAG and perform topological sorting using Kahn’s algorithm. Maintain a DP array storing the earliest completion time for each course. When processing an edge from course u to v, update dp[v] = max(dp[v], dp[u] + time[v]). After processing all nodes, the maximum value in the DP array represents the minimum time to finish all courses.
What is the best approach for Parallel Courses III?
Topological Sort combined with Dynamic Programming is the most efficient and widely accepted solution. Process courses in topological order and maintain the earliest completion time for each course. Each edge updates the dependent course's finish time using the maximum prerequisite completion time. The algorithm runs in O(n + m) time where n is the number of courses and m is the number of prerequisite relations.
Is Parallel Courses III asked at Google/Amazon/Meta?
Graph scheduling and topological sort problems frequently appear in interviews at companies like Google, Amazon, Meta, and Microsoft. Variants of course scheduling and dependency resolution are common system and algorithm questions. This problem tests understanding of DAG processing and dynamic programming.
What data structure is used in Parallel Courses III?
The solution typically uses an adjacency list to represent the graph, a queue for topological sorting, and an array for dynamic programming. The adjacency list efficiently stores prerequisite relationships, while the queue processes nodes with zero in-degree during Kahn’s algorithm.
What is the time complexity of Parallel Courses III?
The optimal solutions run in O(n + m) time and O(n + m) space. Both the topological sort approach and the DFS with memoization approach visit each course and prerequisite relation once. This linear complexity is possible because the course dependency graph forms a directed acyclic graph.

Ready to solve this problem?

Practice Parallel Courses III with our built-in code editor and test cases.

Practice on FleetCode
Previous

Course Schedule III

Next

Maximum Employees to Be Invited to a Meeting