Time Needed to Inform All Employees | Problems

A company has n employees in a tree structure. Employee 0 is head. Return total time needed to inform all employees.

Example: n=6, headID=2, manager=[2,2,-1,2,2,2], informTime=[0,0,1,0,0,0] → Output: 1

Sample Input

—

Sample Output

—

Constraints

1 <= n <= 10^5
0 <= manager[i] < n
0 <= informTime[i] <= 1000

Test Cases

Case 1

Args: [6,2,[2,2,-1,2,2,2],[0,0,1,0,0,0]] Expected: 1

Topics

Graph BFS DFS

DFS

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);
  function dfs(id) {
    let max = 0;
    for (const child of children[id]) max = Math.max(max, dfs(child));
    return informTime[id] + max;
  }
  return dfs(headID);
}

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

Saved in this browser only. Private to you.