Time Needed to Inform All Employees

Intuition

The important thing here is that you don’t pass the informTime to the children. Instead, you process the max informTime of the children seen so far, and then tack on the informTime of your current node which goes to those children in the end.

Runtime

$O(N)$ for traversing through N nodes in the tree, as well as for building the hashmap.

Code

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        d = defaultdict(list)
        for i, m in enumerate(manager):
            d[m].append(i)
 
        def r(cur_manager):
            if cur_manager not in d:
                return 0
 
            nested_inform_time = 0
            for employee in d[cur_manager]:
                nested_inform_time = max(nested_inform_time, r(employee))
            
            return informTime[cur_manager] + nested_inform_time
        
        return r(headID)

---

References

https://leetcode.com/problems/time-needed-to-inform-all-employees/