Leetcode 1376. Time Needed to Inform All Employees

Explanation

The problem revolves around the tree data structure. It describes a company where each employee is represented as a node in the tree and the head of the company is the root of the tree. Each node has a unique ID, a direct manager, and a time required to pass an urgent message to its direct subordinates.

We need to find the maximum time required to inform all employees in the tree about the urgent news. This would essentially mean finding the maximum path length in the tree (as each path edge is weighted by the time taken to pass the message).

Approach

Our goal is to find the longest path in the tree. To achieve this, we can use the Depth-First Search (DFS) algorithm. DFS works by traversing as far as possible down each branch of the tree before backtracking.

Since DFS is inherently recursive, we can implement it using a recursive function. The function will keep track of the time for each employee and ensure that it only traverses to the children of the current employee.

Whenever we visit a node, we check if we have previously computed the maximum time from this node to a leaf node (in memo). If not, we traverse all children of this node (all the Employees which have the current Employee as their Manager) and take the maximum time of all these. Then, we add the time taken by this node (Employee) to convey the message and store this value in our memo.

While doing this, we keep track of the maximum time it takes to reach any leaf node from the root. This value is our answer.

Python Solution

1
2python
3class Solution:
4    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
5
6        graph = collections.defaultdict(list)
7        for i in range(n):
8            if manager[i] != -1:
9                graph[manager[i]].append(i)
10
11        def dfs(i: int) -> int:
12            return max([dfs(j) for j in graph[i]] or [0]) + informTime[i]
13            
14        return dfs(headID)

Java Solution

1
2java
3class Solution {
4    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
5        List<Integer>[] tree = new ArrayList[n];
6        for(int i =0; i<n ;i++){
7            tree[i] = new ArrayList();
8        }
9        
10        
11        int ans = 0;
12        Queue<int[]> q = new LinkedList<int[]>();
13        int head = 0;
14        for(int i=0; i<n;i++){
15            if(manager[i] ==-1){
16                head = i;
17            }
18            else{
19                tree[manager[i]].add(i);
20            }
21        }
22        
23        q.add(new int[]{head,informTime[head]});
24        
25        while(!q.isEmpty()){
26            int[] top = q.poll();
27            ans = Math.max(ans,top[1]);
28            for(int nei : tree[top[0]]){
29                q.add(new int[]{nei,top[1] + informTime[nei]});
30            }
31        }
32        
33        return ans;
34    }
35}

JavaScript Solution

1
2js
3var numOfMinutes = function(n, headID, manager, informTime) {
4    const graph = new Map();
5    let max = Number.MIN_VALUE;
6
7    for (let i = 0; i < n; i++) {
8        if (graph.has(manager[i])) {
9            graph.get(manager[i]).push(i);
10        } else {
11            graph.set(manager[i], [i]);
12        }
13    }
14
15    const dfs = (index, sum) => {
16        if (!graph.has(index)) {
17            max = Math.max(max, sum);
18            return;
19        }
20        
21        for (const m of graph.get(index)) {
22            dfs(m, sum+informTime[m]);
23        }
24    }
25    
26    dfs(headID, informTime[headID]);
27    return max;
28};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
6        vector<vector<int>> sub(n);
7        int ans = 0;
8        
9        for(int i=0;i<n;i++){
10            if(manager[i] != -1)
11                sub[manager[i]].push_back(i);
12        }
13        
14        queue<pair<int,int>> q;
15        q.push({headID,informTime[headID]});
16        
17        while(!q.empty()){
18            pair<int,int> cur = q.front();
19            q.pop();
20            ans = max(ans,cur.second);
21            
22            for(int v : sub[cur.first]){
23                q.push({v,cur.second+informTime[v]});
24            }
25        }
26       
27        return ans;
28    }
29};

C# Solution

1
2csharp
3public class Solution {
4    public int NumOfMinutes(int n, int headID, int[] manager, int[] informTime) {
5        Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>();
6        int totalTime = 0;
7
8        for(int i = 0; i < n; i++)
9        {
10            if(manager[i] != -1)
11            {
12                if(graph.ContainsKey(manager[i]))
13                    graph[manager[i]].Add(i);
14                else
15                {
16                    graph[manager[i]] = new List<int> {i};
17                }
18            }
19        }
20
21        Queue<(int, int)> informQueue = new Queue<(int, int)>();
22        informQueue.Enqueue((headID, informTime[headID]));
23        
24        while(informQueue.Any())
25        {
26            var currentEmployee = informQueue.Dequeue();
27            totalTime = Math.Max(totalTime, currentEmployee.Item2);
28            
29            if(graph.ContainsKey(currentEmployee.Item1))
30            {
31                foreach(int subordinate in graph[currentEmployee.Item1])
32                {
33                    informQueue.Enqueue((subordinate, currentEmployee.Item2 + informTime[subordinate]));
34                }
35            }
36        }
37        
38        return totalTime;
39    }
40}

These methods first construct the subordinates (direct & indirect) for each manager. Then, based on the tree structure, consideration is given to all path times informing each employee, moving in a BFS manner from the CEO to employees. The maximum time required among all the paths is the desired output.Each of the solutions iterates through the list of managers to construct a dictionary/graph with the manager as the key and the ids of their respective subordinates as values. As a result, this dictionary/graph represents the structure of our tree, with managers as parents and their subordinates as children.

To calculate the maximum path length, we start from the root of the tree (i.e. the head of the company) and traverse through its branches using either Depth-First Search (DFS) or Breadth-First Search (BFS).

In the Python and JavaScript solutions, DFS is used. The helper function dfs takes two arguments: index (which represents the id of the current employee), and sum (which is the total time required to pass the news to the current employee from the head of the company). For each node, we add the time required to pass on the message to the total time (sum), then recursively call dfs for each of its children. The variable max is updated with the maximum time whenever a dead-end is reached (i.e there is no more subordinates to pass on news to). The helper function initially starts with headID as the index and informTime[headID] as the sum.

In the Java and C# solutions, BFS is used. Instead of a helper function, a queue is used to iteratively traverse the tree from the root to the leaves. For each node, we add its time to the total time taken by its parent to receive the news. Then, all its children are added to the queue with their respective total times. The maximum time encountered in this process is returned as the final result.

In the C++ solution, BFS is also used, but pair<int, int> is used to hold the current node and its total time. In addition, the 'sub' variable holds the indices of the child nodes of each node , and 'ans' holds the maximum time. The queue is looped, with each iteration adding the children and their cumulative times to the queue and updating 'ans'.

Thus, using DFS or BFS, we can solve this problem efficiently in different programming languages.

It's important to note that these approaches all require O(n) time complexity, where n is the number of employees in the company, because we need to traverse every single node of the tree to find the maximal time, and use O(n) space complexity as we store the subordinates for each employee. This could be further optimized based on specific use-cases, but for a general solution, these are pretty solid!


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫