2050. Parallel Courses III - Explanation

1. Depth First Search

Intuition

Each course has a duration, and we can take courses in parallel as long as prerequisites are satisfied. The minimum time to finish all courses equals the longest path in the dependency graph, where path length is the sum of course durations along that path.

For each course, we need to find the maximum time required to complete it and all its dependent courses. Using DFS with memoization, we compute the total time starting from each course by taking the maximum of all paths through its dependencies, plus the course's own duration.

Algorithm

Build an adjacency list where each course points to its dependent courses.
Use a hash map to cache the maximum completion time starting from each course.
For each course, run dfs:
- Return the cached value if already computed.
- Recursively compute the maximum time through all dependent courses.
- Add the current course's duration to get the total time from this course.
- Cache and return the result.
Return the maximum value among all courses' completion times.

class Solution:
    def minimumTime(self, n: int, relations: list[list[int]], time: list[int]) -> int:
        adj = defaultdict(list)
        for src, dst in relations:
            adj[src].append(dst)

        max_time = {}

        def dfs(src):
            if src in max_time:
                return max_time[src]
            res = time[src - 1]
            for nei in adj[src]:
                res = max(res, time[src - 1] + dfs(nei))
            max_time[src] = res
            return res

        for i in range(1, n + 1):
            dfs(i)

        return max(max_time.values())

Time & Space Complexity

Time complexity: $O(V + E)$
Space complexity: $O(V + E)$

Where $V$ is the number of courses and $E$ is the number of prerequisites.

2. Iterative DFS

Intuition

The recursive DFS can be converted to an iterative version using an explicit stack. This avoids potential stack overflow for deep recursion and gives more control over the traversal order.

We use a two-phase approach: first push a node onto the stack, then when we pop it again after processing its children, we compute its final value. A "processed" flag distinguishes between these two phases.

Algorithm

Build an adjacency list for course dependencies.
Initialize arrays to track the maximum time for each course and whether each course is fully processed.
For each unvisited course, start an iterative dfs:
- Push the course onto the stack.
- When popping, if not processed, mark as processing and push back, then push all unvisited neighbors.
- When popping a processed node, compute its max time as its duration plus the maximum of its neighbors' times.
Return the maximum completion time across all courses.

class Solution:
    def minimumTime(self, n: int, relations: list[list[int]], time: list[int]) -> int:
        adj = [[] for _ in range(n)]
        for src, dst in relations:
            adj[src - 1].append(dst - 1)

        maxTime = [-1] * n
        processed = [False] * n

        for i in range(n):
            if maxTime[i] == -1:
                stack = [i]
                while stack:
                    node = stack.pop()
                    if processed[node]:
                        best = 0
                        for nei in adj[node]:
                            best = max(best, maxTime[nei])
                        maxTime[node] = time[node] + best
                    else:
                        processed[node] = True
                        stack.append(node)
                        for nei in adj[node]:
                            if maxTime[nei] == -1:
                                stack.append(nei)
        return max(maxTime)

Time & Space Complexity

Time complexity: $O(V + E)$
Space complexity: $O(V + E)$

Where $V$ is the number of courses and $E$ is the number of prerequisites.

3. Topological Sort (Kahn's Algorithm)

Intuition

Instead of working backwards from end nodes (DFS approach), we can work forwards from start nodes using topological sort. Kahn's algorithm processes nodes in dependency order, ensuring that when we process a course, all its prerequisites have already been processed.

For each course, we track the maximum time needed to reach it (including its own duration). When we process a course, we update all its dependents by propagating the maximum completion time. This naturally computes the longest weighted path through the graph.

Algorithm

Build an adjacency list and compute in-degrees for all courses.
Initialize each course's max time to its own duration.
Add all courses with in-degree 0 to the queue.
Process courses in topological order:
- For each dependent course, update its max time to be the maximum of its current value and the predecessor's time plus its own duration.
- Decrement the in-degree and add to the queue when it reaches 0.
Return the maximum completion time across all courses.

class Solution:
    def minimumTime(self, n: int, relations: list[list[int]], time: list[int]) -> int:
        adj = [[] for _ in range(n)]
        indegree = [0] * n
        maxTime = time[:]

        for src, dst in relations:
            adj[src - 1].append(dst - 1)
            indegree[dst - 1] += 1

        queue = deque([i for i in range(n) if indegree[i] == 0])
        while queue:
            node = queue.popleft()
            for nei in adj[node]:
                maxTime[nei] = max(maxTime[nei], maxTime[node] + time[nei])
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    queue.append(nei)

        return max(maxTime)

Time & Space Complexity

Time complexity: $O(V + E)$
Space complexity: $O(V + E)$

Where $V$ is the number of courses and $E$ is the number of prerequisites.

Common Pitfalls

Confusing This With the Basic Parallel Courses Problem

Unlike the simpler version where each course takes one semester, this problem assigns different durations to each course. The answer is not just the longest path by node count, but the longest path by total time. Each course's duration must be added to the path weight.

Incorrect Initialization of Course Times

When using topological sort, each course's initial time should be its own duration, not zero. Failing to initialize maxTime[i] = time[i] means courses with no prerequisites will incorrectly have zero completion time.

Building the Adjacency List in the Wrong Direction

For the DFS approach, edges should point from prerequisites to dependent courses (forward direction). For some formulations, you might need to reverse this. Mixing up directions leads to computing minimum time to reach a course instead of minimum time from a course to complete all dependents.

Forgetting That Parallel Execution Means Taking the Maximum

When a course has multiple prerequisites, it cannot start until all prerequisites complete. This means taking the maximum completion time among all prerequisites, not the sum. Using addition instead of max will drastically overcount the total time.

Off-By-One Errors With 1-Indexed Courses

Course numbers are often 1-indexed in the input, but the time array is 0-indexed. Accessing time[course] instead of time[course - 1] causes array index out of bounds or incorrect time values.