Problem

A company has n employees with a unique ID for each employee from 0 to n - 1. The head of the company is the one with headID.

Each employee has one direct manager given in the manager array where manager[i] is the direct manager of the i-th employee, manager[headID] = -1. Also, it is guaranteed that the subordination relationships have a tree structure.

The head of the company wants to inform all the company employees of an urgent piece of news. He will inform his direct subordinates, and they will inform their subordinates, and so on until all employees know about the urgent news.

The i-th employee needs informTime[i] minutes to inform all of his direct subordinates (i.e., After informTime[i] minutes, all his direct subordinates can start spreading the news).

Return the number of minutes needed to inform all the employees about the urgent news.

Examples

Example 1:

1
2
3

Input: n = 1, headID = 0, manager = [-1], informTime = [0]
Output: 0
Explanation: The head of the company is the only employee in the company.

Example 2:

graph TD;
	A(2) --- B(0) & C(1) & D(3) & E(4) & F(5)
  
1
2
3
4

Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
Output: 1
Explanation: The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all.
The tree structure of the employees in the company is shown.

Constraints:

  • 1 <= n <= 10^5
  • 0 <= headID < n
  • manager.length == n
  • 0 <= manager[i] < n
  • manager[headID] == -1
  • informTime.length == n
  • 0 <= informTime[i] <= 1000
  • informTime[i] == 0 if employee i has no subordinates.
  • It is guaranteed that all the employees can be informed.

Solution

This problem can be solved using a tree traversal mechanism. Since the structure forms a tree where each employee has a manager (except the head), we can represent this relationship as an adjacency list. Specifically:

  1. We will build the adjacency list representation where each employee points to their direct subordinates.
  2. Once the adjacency list is constructed, we use Depth First Search (DFS) or Breadth First Search (BFS) to traverse the tree.
  3. During traversal, calculate the total time required to inform each employee recursively. For a manager, the total time required is the sum of their informTime and the maximum time it takes for any of their subordinates to spread the news.

Method 1 - DFS

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public class Solution {
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        // Build adjacency list for the tree
        Map<Integer, List<Integer>> adj = new HashMap<>();
        for (int i = 0; i < n; i++) {
            adj.putIfAbsent(i, new ArrayList<>());
            if (manager[i] != -1) {
                adj.get(manager[i]).add(i);
            }
        }
        
        // DFS function to calculate maximum time
        return dfs(headID, adj, informTime);
    }

    private int dfs(int emp, Map<Integer, List<Integer>> adj, int[] informTime) {
        // If the employee has no subordinates, return 0
        if (!adj.containsKey(emp) || adj.get(emp).isEmpty()) {
            return 0;
        }
        // Calculate maximum time required for all subordinates
        int ans = 0;
        for (int sub : adj.get(emp)) {
            ans = Math.max(ans, dfs(sub, adj, informTime));
        }
        return ans + informTime[emp];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        # Build adjacency list for the tree
        adj: Dict[int, List[int]] = {i: [] for i in range(n)}
        for emp in range(n):
            if manager[emp] != -1:
                adj[manager[emp]].append(emp)
        
        def dfs(emp: int) -> int:
            # If the employee has no subordinates, return 0
            if not adj[emp]:
                return 0
            # Calculate maximum time required for all subordinates
            return max(dfs(sub) for sub in adj[emp]) + informTime[emp]

        # Start DFS from the head of the company
        return dfs(headID)

Complexity

  • ⏰ Time complexity: O(n). Building the adjacency list takes O(n), and traversing through all employees takes O(n) since the tree has n nodes.
  • 🧺 Space complexity: O(n). For the adjacency list and the recursive call stack (in case of DFS).