# Parallel Courses III
**Difficulty:** HARD
[External](https://leetcode.com/problems/parallel-courses-iii)
Canonical: https://scaleengineer.com/dsa/problems/parallel-courses-iii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Topological Sort](https://scaleengineer.com/algorithms/topological-sort)
**Data structures:** Array, Graph
**Companies:** [Snowflake](https://scaleengineer.com/companies/snowflake), [TikTok](https://scaleengineer.com/companies/tiktok), [Citadel](https://scaleengineer.com/companies/citadel), [Snap](https://scaleengineer.com/companies/snap), [Two Sigma](https://scaleengineer.com/companies/two-sigma), [Stripe](https://scaleengineer.com/companies/stripe), [Acko](https://scaleengineer.com/companies/acko)
---
## Problem
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:**

**![](https://assets.glich.co/dsa/parallel-courses-iii/image0.png)** 

**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:**

**![](https://assets.glich.co/dsa/parallel-courses-iii/image1.png)** 

**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.

# Approaches
## DFS with Memoization (Top-Down DP)
This problem can be framed as finding the longest path in a Directed Acyclic Graph (DAG), where the 'weight' of each node is the time required to complete the corresponding course. A recursive Depth-First Search (DFS) approach is a natural way to solve this. To prevent recomputing the completion time for the same course multiple times, which would lead to an exponential time complexity, we use memoization to store and reuse the results.
**Time:** O(V + E), where V is the number of courses (n) and E is the number of relations. Building the graph takes `O(E)`. The DFS function with memoization ensures that each course (node) and prerequisite relationship (edge) is processed exactly once. · **Space:** O(V + E), where V is the number of courses (n) and E is the number of relations. This is for storing the adjacency list (`O(V + E)`), the memoization array (`O(V)`), and the recursion stack (`O(V)` in the worst case).
**Pros:** Conceptually straightforward, as it directly translates the recursive nature of the problem.; Easy to implement once the graph representation is decided.
**Cons:** Recursive calls have slightly more overhead than an iterative approach.; Can lead to a `StackOverflowError` on very deep graphs, though the problem constraints make this less likely.
### Explanation
In this top-down dynamic programming approach, we define a function, say `dfs(course)`, which calculates the minimum time required to complete that `course` and all of its prerequisites. 

- The base case for the recursion is a course with no prerequisites. Its completion time is simply its own `time`.
- For a course with prerequisites, its start time is determined by the prerequisite that finishes last. So, `startTime(course) = max(completionTime(prereq))` for all its prerequisites.
- The completion time for the course is then `startTime(course) + time(course)`.

We use a memoization array, `memo`, to store the calculated completion times. Before computing `dfs(course)`, we check if `memo[course]` has a stored value. If so, we return it immediately. Otherwise, we compute the value, store it in `memo`, and then return it.

To implement this, we first need to build a graph representation that allows us to easily find the prerequisites for any given course. An adjacency list where `prereqGraph[i]` stores the list of prerequisites for course `i` is suitable. The final answer is the maximum completion time among all courses.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int minimumTime(int n, int[][] relations, int[] time) {
        List<List<Integer>> prereqGraph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            prereqGraph.add(new ArrayList<>());
        }
        for (int[] relation : relations) {
            // relation[0] is a prereq for relation[1]
            prereqGraph.get(relation[1]).add(relation[0]);
        }

        int[] memo = new int[n + 1];
        int maxTotalTime = 0;
        for (int i = 1; i <= n; i++) {
            maxTotalTime = Math.max(maxTotalTime, dfs(i, prereqGraph, time, memo));
        }
        return maxTotalTime;
    }

    private int dfs(int course, List<List<Integer>> prereqGraph, int[] time, int[] memo) {
        if (memo[course] != 0) {
            return memo[course];
        }

        int maxPrereqTime = 0;
        for (int prereq : prereqGraph.get(course)) {
            maxPrereqTime = Math.max(maxPrereqTime, dfs(prereq, prereqGraph, time, memo));
        }

        // The time to complete this course is its own time plus the time of the longest prerequisite path.
        memo[course] = maxPrereqTime + time[course - 1];
        return memo[course];
    }
}
```
### Algorithm
- Build a prerequisite graph (adjacency list `prereqGraph`) where `prereqGraph[i]` contains the list of prerequisites for course `i`.
- Initialize a memoization array `memo` of size `n+1` to store the calculated longest path (completion time) for each course.
- Iterate through each course from 1 to `n`. For each course `i`, call a recursive helper function `dfs(i, prereqGraph, time, memo)`.
- The `dfs` function:
    - If `memo[course]` is already computed, return it.
    - Find the maximum completion time among all prerequisites by recursively calling `dfs` on them. Let this be `maxPrereqTime`.
    - The completion time for the current course is `maxPrereqTime + time[course - 1]`.
    - Store this result in `memo[course]` and return it.
- After the loop, the overall minimum time is the maximum value found across all DFS calls.

## Topological Sort (Kahn's Algorithm)
This is an iterative, bottom-up dynamic programming approach based on topological sorting (specifically, Kahn's algorithm). We process courses in an order such that all prerequisites of a course are processed before the course itself. This allows us to build up the completion times from the starting courses (those with no prerequisites) towards the final courses in the dependency chain.
**Time:** O(V + E), where V is the number of courses (n) and E is the number of relations. Building the graph and in-degrees takes `O(V + E)`. The topological sort processes each node and edge once. Finding the max at the end takes `O(V)`. · **Space:** O(V + E), where V is the number of courses (n) and E is the number of relations. This space is used for the adjacency list (`O(V + E)`), the in-degree array (`O(V)`), the queue (`O(V)`), and the completion time array (`O(V)`).
**Pros:** Iterative approach avoids recursion overhead and the risk of stack overflow.; Generally considered a very robust and efficient method for problems on DAGs.; The `completionTime` array directly computes the longest path to each node from the source nodes.
**Cons:** Requires building both an adjacency list and an in-degree array, which can be slightly more setup than the recursive approach.
### Explanation
We first model the course dependencies as a directed graph. We need an adjacency list `adj` where `adj[u]` stores the list of courses that depend on `u`, and an `inDegree` array where `inDegree[v]` stores the number of prerequisites for course `v`. We also use a `completionTime` array to store the earliest possible completion time for each course.

The algorithm starts by identifying all courses with an in-degree of 0. These are the courses with no prerequisites. We add them to a queue and set their `completionTime` to their own `time`.

We then process the queue. For each course `u` we dequeue, we consider it 'completed'. We then look at all its successor courses `v`. For each `v`, we update its potential completion time. The start time for `v` must be at least `completionTime[u]`. Therefore, the completion time for `v` through the path from `u` is `completionTime[u] + time[v-1]`. Since `v` might have multiple prerequisites, we take the maximum of these potential completion times: `completionTime[v] = max(completionTime[v], completionTime[u] + time[v-1])`.

We also decrement the in-degree of `v`. If the in-degree of `v` becomes 0, it means all its prerequisites have been processed, so we can now add `v` to the queue. We continue this until the queue is empty. The overall minimum time to finish all courses is the maximum value in the `completionTime` array.

```java
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
    public int minimumTime(int n, int[][] relations, int[] time) {
        List<List<Integer>> adj = new ArrayList<>();
        int[] inDegree = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }

        for (int[] relation : relations) {
            int prev = relation[0];
            int next = relation[1];
            adj.get(prev).add(next);
            inDegree[next]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        int[] completionTime = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
                completionTime[i] = time[i - 1];
            }
        }

        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : adj.get(u)) {
                completionTime[v] = Math.max(completionTime[v], completionTime[u] + time[v - 1]);
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    queue.offer(v);
                }
            }
        }

        int maxTotalTime = 0;
        for (int i = 1; i <= n; i++) {
            maxTotalTime = Math.max(maxTotalTime, completionTime[i]);
        }
        return maxTotalTime;
    }
}
```
### Algorithm
- Build an adjacency list `adj` and an `inDegree` array from the `relations`. `adj[u]` will store courses that have `u` as a prerequisite.
- Initialize a queue and add all courses `i` with `inDegree[i] == 0`.
- Initialize a `completionTime` array. For each course `i` added to the queue, set `completionTime[i] = time[i-1]`.
- While the queue is not empty:
    - Dequeue a course `u`.
    - For each neighbor `v` of `u`:
        - Update `completionTime[v] = max(completionTime[v], completionTime[u] + time[v-1])`.
        - Decrement `inDegree[v]`.
        - If `inDegree[v]` becomes 0, enqueue `v`.
- The result is the maximum value in the `completionTime` array.

# Solutions
### Java

```java
class Solution {
public
  int minimumTime(int n, int[][] relations, int[] time) {
    List<Integer>[] g = new List[n];
    Arrays.setAll(g, k->new ArrayList<>());
    int[] indeg = new int[n];
    for (int[] e : relations) {
      int a = e[0] - 1, b = e[1] - 1;
      g[a].add(b);
      ++indeg[b];
    }
    Deque<Integer> q = new ArrayDeque<>();
    int[] f = new int[n];
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      int v = indeg[i], t = time[i];
      if (v == 0) {
        q.offer(i);
        f[i] = t;
        ans = Math.max(ans, t);
      }
    }
    while (!q.isEmpty()) {
      int i = q.pollFirst();
      for (int j : g[i]) {
        f[j] = Math.max(f[j], f[i] + time[j]);
        ans = Math.max(ans, f[j]);
        if (--indeg[j] == 0) {
          q.offer(j);
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumTime(int n, vector<vector<int>> &relations, vector<int> &time) {
    vector<vector<int>> g(n);
    vector<int> indeg(n);
    for (auto &e : relations) {
      int a = e[0] - 1, b = e[1] - 1;
      g[a].push_back(b);
      ++indeg[b];
    }
    queue<int> q;
    vector<int> f(n);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      int v = indeg[i], t = time[i];
      if (v == 0) {
        q.push(i);
        f[i] = t;
        ans = max(ans, t);
      }
    }
    while (!q.empty()) {
      int i = q.front();
      q.pop();
      for (int j : g[i]) {
        if (--indeg[j] == 0) {
          q.push(j);
        }
        f[j] = max(f[j], f[i] + time[j]);
        ans = max(ans, f[j]);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int: g = defaultdict(list) indeg = [0] * n for a, b in relations: g[a - 1]. append(b - 1) indeg[b - 1] += 1 q = deque() f = [0] * n ans = 0 for i, (v, t) in enumerate(zip(indeg, time)): if v == 0: q . append(i) f[i] = t ans = max(ans, t) while q: i = q . popleft() for j in g[i]: f[j] = max(f[j], f[i] + time[j]) ans = max(ans, f[j]) indeg[j] -= 1 if indeg[j] == 0: q . append(j) return ans

```