Time Needed to Inform All Employees

How it works

Instead of building an explicit adjacency list, we can traverse from each employee up to the root, caching results along the way. For any employee, their total inform time is their own inform time plus their manager's total inform time.

We use the manager array directly for traversal and cache computed results in the inform time array itself. Once an employee's path to root is computed, we mark their manager as -1 to indicate completion. This approach uses path compression similar to Union-Find.

Steps

1. For each employee, recursively compute their total time by following the manager chain to the root.
2. Base case: if an employee has no manager (-1), return their inform time.
3. Add the manager's total time to the current employee's inform time.
4. Mark the employee's manager as -1 to cache the result and prevent recomputation.
5. Track the maximum inform time seen across all employees.
6. Return the maximum time.

Complexity

• Time complexity: O(n)
• Space complexity: O(n) for recursion stack.

Things to watch for

Summing Instead of Taking Maximum Over Children

The total time is the longest path from root to any leaf, not the sum of all inform times. When a manager informs multiple subordinates, they are informed simultaneously. You should take the maximum time among all subtrees, not add them together. Using sum instead of max produces answers that are way too large.

Forgetting That Leaf Nodes Have Zero Inform Time

Employees with no subordinates (leaf nodes) have informTime[i] = 0. When building the adjacency list or computing times, ensure you handle this correctly. Some solutions mistakenly add inform time even for leaves or skip leaves entirely, leading to incorrect results.

Not Building the Adjacency List Correctly

The manager array gives parent pointers, but for DFS/BFS you need children pointers. A common mistake is iterating incorrectly when building the adjacency list or accidentally including the head in some manager's list. The head has manager[headID] = -1, so you must skip adding edges for the head node.

from typing import List

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        def dfs(node):
            if manager[node] != -1:
                informTime[node] += dfs(manager[node])
                manager[node] = -1
            return informTime[node]

        res = 0
        for node in range(n):
            res = max(res, dfs(node))
        return res

class Solution {
public:
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        function<int(int)> dfs = [&](int node) {
            if (manager[node] != -1) {
                informTime[node] += dfs(manager[node]);
                manager[node] = -1;
            }
            return informTime[node];
        };

        int res = 0;
        for (int node = 0; node < n; ++node) {
            res = max(res, dfs(node));
        }
        return res;
    }
};