Time Needed to Inform All Employees Medium 0 attempts
LeetCode ↗

Time Needed to Inform All Employees

Medium GraphBFSDFS LeetCode

A company's n employees form a tree-shaped management hierarchy, with employee headID as the head. When the head starts spreading news, each manager needs some time to inform their direct subordinates before the news can continue further down the chain. Find the total time needed for every employee to be informed.

Input Format
Implement numOfMinutes(n, headID, manager, informTime). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
n = 6
headID = 2
manager = [2,2,-1,2,2,2]
informTime = [0,0,1,0,0,0]
Output
1

Example 2

Input
n = 1
headID = 0
manager = [-1]
informTime = [0]
Output
0
Constraints
  • 1 <= n <= 10^5
  • 0 <= headID < n; manager[headID] == -1
  • Every other manager entry is in [0,n-1]; the hierarchy forms one rooted tree.
  • 0 <= informTime[i] <= 1000; employees with no subordinates have informTime[i] == 0.
Test Cases (2)
Case 1
Args: [6,2,[2,2,-1,2,2,2],[0,0,1,0,0,0]] Expected: 1
Case 2
Args: [1,0,[-1],[0]] Expected: 0
Topics
GraphBFSDFS

Iterative DFS with Arrival Times

A subordinate receives the news after its manager’s arrival time plus the manager’s informTime. Track those arrival times and return their maximum.

javascript
function numOfMinutes(n, headID, manager, informTime) {
  const children=Array.from({length:n},()=>[]);
  for(let i=0;i<n;i++)if(manager[i]!==-1)children[manager[i]].push(i);
  const stack=[[headID,0]];let total=0;
  while(stack.length){const [id,time]=stack.pop();total=Math.max(total,time);for(const child of children[id])stack.push([child,time+informTime[id]]);}
  return total;
}

Time: O(n) | Space: O(n)

Saved in this browser only. Private to you.

JavaScript