Watch 10 video solutions for Parallel Courses III, a hard level problem involving Array, Dynamic Programming, Graph. This walkthrough by NeetCodeIO has 19,671 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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 * 1040 <= relations.length <= min(n * (n - 1) / 2, 5 * 104)relations[j].length == 21 <= prevCoursej, nextCoursej <= nprevCoursej != nextCoursej[prevCoursej, nextCoursej] are unique.time.length == n1 <= time[i] <= 104Problem 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 | Time | Space | When to Use |
|---|---|---|---|
| Topological Sort with Dynamic Programming | O(n + m) | O(n + m) | Best general solution for DAG scheduling problems with prerequisites |
| DFS with Memoization | O(n + m) | O(n + m) | Useful when modeling the problem as longest path in a DAG using recursion |