< Back





1376. Time Needed to Inform All Employees

We have a company with 0 to n-1 employees, a head honcho defined by headID, a list of managers,
and the time it takes to inform each employee with new info - informTime. The managers[] list defines
the employee : manager relationship at manager[i] - for the i-th employee their manager is
manager[i]. We're asked to find the time needed to inform all employees.

Well, all employees won't be informed until the last one is informed - so whichever path in this tree
takes the longest. How do we know it's a tree? The manager[i] list defines directed edges from
manager -> subordinate. Given these variables, we construct a graph of directed edges and then
conduct BFS.

As we conduct the BFS, we maintain the longest length of time it takes to inform all employees on a
particular path.

The solution is as follows:


  from collections import defaultdict

  class Solution:
      def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
          ans = 0
          graph = defaultdict(list)

          for i in range(n):
              j = manager[i]

              if j == -1:
                  continue

              graph[j].append(i)

          queue = [(headID, informTime[headID])]

          while queue:
              curr_queue, queue = queue, []

              for employee, time in curr_queue:
                  ans = max(ans, time)

                  for subordinate in graph[employee]:
                      queue.append((subordinate, informTime[subordinate] + time))

          return ans


_ Time Complexity:

  O(n) - BFS takes O(n) time to traverse the graph. Constructing the graph takes O(n) time.

_ Space Complexity:

  O(n) - We store the graph in an adjaceny list. The queue can store up to n elements.