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.