MANG Problem #48: Parallel Courses III (Hard)

1. Problem Statement

Mental Model

Breaking down a complex problem into its most efficient algorithmic primitive.

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] = [prevCourse_j, nextCourse_j], denoting that course prevCourse_j has to be completed before course nextCourse_j starts.

You are also given a 0-indexed integer array time where time[i] denotes how many months it takes to complete the (i+1)-th course.

You may take any number of courses simultaneously. Return the minimum number of months needed to complete all the courses.

2. Approach: Topological Sort + DP

This problem asks for the longest path (critical path) in a Directed Acyclic Graph (DAG). Since we can take courses in parallel, the start time of a course is determined by the maximum completion time of all its prerequisites.

Build Graph: Standard Adjacency List and inDegree array.
DP Array: maxTime[i] stores the maximum time required to complete course i (including all its prerequisites). Initialize it with time[i].
Kahn's Algorithm:
- Push all courses with inDegree == 0 to a queue.
- When processing a course u, look at its neighbors v.
- The new time to complete v is max(maxTime[v], maxTime[u] + time[v]). Update maxTime[v].
- Decrement inDegree[v]. If it hits 0, push to queue.
Result: Return the maximum value in the maxTime array.

3. Java Implementation

public int minimumTime(int n, int[][] relations, int[] time) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
    
    int[] inDegree = new int[n + 1];
    for (int[] rel : relations) {
        adj.get(rel[0]).add(rel[1]);
        inDegree[rel[1]]++;
    }
    
    int[] maxTime = new int[n + 1];
    Queue<Integer> q = new LinkedList<>();
    
    // Initialize base cases
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == 0) {
            q.offer(i);
            maxTime[i] = time[i - 1]; // time is 0-indexed
        }
    }
    
    while (!q.isEmpty()) {
        int u = q.poll();
        for (int v : adj.get(u)) {
            // The time to finish V is the max of its current known time, 
            // or the time to finish U plus V's duration.
            maxTime[v] = Math.max(maxTime[v], maxTime[u] + time[v - 1]);
            
            inDegree[v]--;
            if (inDegree[v] == 0) {
                q.offer(v);
            }
        }
    }
    
    int result = 0;
    for (int i = 1; i <= n; i++) {
        result = Math.max(result, maxTime[i]);
    }
    return result;
}

4. 5-Minute "Video-Style" Walkthrough

The "Aha!" Moment: If course C depends on course A (takes 10 months) and course B (takes 2 months), you can't start C until month 10. The dependency with the longest duration is the bottleneck.
The DP State: maxTime[i] accumulates the bottleneck. Every time an edge U -> V is processed, we check if U's completion time forces V to finish later than we previously thought.
The Parallel Processing: Because we use Kahn's algorithm, we are guaranteed that when we pull a course out of the queue, all of its prerequisites have been fully evaluated, so its maxTime is completely finalized.

5. Interview Discussion

Interviewer: "What is the time complexity?"
You: "O(V + E) where V is the number of courses and E is the number of dependencies. We visit each course and each dependency edge exactly once."
Interviewer: "Can this be solved with DFS?"
You: "Yes, we can use DFS with Memoization. dfs(node) would return the max time to finish that node by recursively taking the max of dfs(neighbor) + time[node]. Both approaches are O(V + E), but BFS (Kahn's) avoids deep recursion stacks."

5. Verbal Interview Script (Staff Tier)

Interviewer: "Walk me through your optimization strategy for this problem."

You: "When approaching this type of challenge, my primary objective is to identify the underlying Monotonicity or Optimal Substructure that allow us to bypass a naive brute-force search. In my implementation of 'MANG Problem #48: Parallel Courses III (Hard)', I focused on reducing the time complexity by leveraging a Dynamic Programming state transition. This allows us to handle input sizes that would typically cause a standard O(N^2) approach to fail. Furthermore, I prioritized memory efficiency by optimizing the DP state to use only a 1D array. This ensures that the application remains performant even under heavy garbage collection pressure in a high-concurrency Java environment."

6. Staff-Level Interview Follow-Ups

Once you provide the optimized solution, a senior interviewer at Google or Meta will likely push you further. Here is how to handle the most common follow-ups:

Follow-up 1: "How does this scale to a Distributed System?"

If the input data is too large to fit on a single machine (e.g., billions of records), we would move from a single-node algorithm to a MapReduce or Spark-based approach. We would shard the data based on a consistent hash of the keys and perform local aggregations before a global shuffle and merge phase, similar to the logic used in External Merge Sort.

Follow-up 2: "What are the Concurrency implications?"

In a multi-threaded Java environment, we must ensure that our state (e.g., the DP table or the frequency map) is thread-safe. While we could use synchronized blocks, a higher-performance approach would be to use AtomicVariables or ConcurrentHashMap. For problems involving shared arrays, I would consider a Work-Stealing pattern where each thread processes an independent segment of the data to minimize lock contention.

7. Performance Nuances (The Java Perspective)

Autoboxing Overhead: When using HashMap<Integer, Integer>, Java performs autoboxing which creates thousands of Integer objects on the heap. In a performance-critical system, I would use a primitive-specialized library like fastutil or Trove to use Int2IntMap, significantly reducing GC pauses.
Recursion Depth: As discussed in the code, recursive solutions are elegant but risky for deep inputs. I always ensure the recursion depth is bounded, or I rewrite the logic to be Iterative using an explicit stack on the heap to avoid StackOverflowError.

Key Takeaways

Push all courses with inDegree == 0 to a queue.
When processing a course u, look at its neighbors v.
The new time to complete v is max(maxTime[v], maxTime[u] + time[v]). Update maxTime[v].