Problem URL: Time needed to inform all employees

We will start BFS from the manager with no manager. We will keep track of the maximum time taken to inform all the employees.

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        graph = collections.defaultdict(list)
        for i, m in enumerate(manager):
            graph[m].append(i)

        q = collections.deque([(headID, 0)])
        maxTime = 0

        while q:
            emp, time = q.popleft()
            maxTime = max(maxTime, time)
            for sub in graph[emp]:
                q.append((sub, time + informTime[emp]))

        return maxTime

Time complexity: O(n)
Space complexity: O(n)