# Time Needed to Inform All Employees
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/time-needed-to-inform-all-employees)
Canonical: https://scaleengineer.com/dsa/problems/time-needed-to-inform-all-employees
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree
---
## 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.

**Example 1:**

**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:**

![](https://assets.glich.co/dsa/time-needed-to-inform-all-employees/image0.png) 

**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 <= 105`
* `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.

# Approaches
## Bottom-Up Path Traversal
This approach calculates the time required for the news to reach each individual employee and then finds the maximum among them. For every employee, it traverses up the hierarchy to the head of the company, summing the `informTime` of each manager along the path.
**Time:** O(N * H), where N is the number of employees and H is the height of the management tree. In the worst case of a skewed tree (like a linked list), H can be O(N), leading to a time complexity of O(N^2). · **Space:** O(1) extra space. We only use a few variables to track the current employee and time during the traversal, not counting the input arrays.
**Pros:** Simple to conceptualize and implement.; Very low memory overhead, using O(1) extra space.
**Cons:** Highly inefficient for deep or skewed trees, leading to a worst-case time complexity of O(N^2).; Performs many redundant calculations. The time for a manager's branch to be informed is recalculated for each of their subordinates.
### Explanation
The core idea is that the time for an employee `i` to be informed is the sum of the `informTime` of all their managers up to the company head. We can iterate through each employee from `0` to `n-1`. For each employee `i`, we start a loop that moves from `i` to `manager[i]`, then to `manager[manager[i]]`, and so on, until we reach the head (`manager[...]==-1`). In this loop, we accumulate the `informTime` of the managers. We keep a global variable, `maxTime`, to store the maximum time calculated across all employees. After checking all employees, `maxTime` will hold the result. This method is simple to understand but inefficient because it repeatedly calculates the time for the upper parts of the management tree. For example, if employees A and B have the same manager M, the path from M to the head is calculated twice.

```java
class Solution {
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        int maxTime = 0;
        for (int i = 0; i < n; i++) {
            int currentTime = 0;
            int currentEmployee = i;
            // Traverse up the management chain
            while (manager[currentEmployee] != -1) {
                currentEmployee = manager[currentEmployee];
                currentTime += informTime[currentEmployee];
            }
            maxTime = Math.max(maxTime, currentTime);
        }
        return maxTime;
    }
}
```
### Algorithm
*   Initialize a variable `maxTime` to 0.
*   Iterate through each employee `i` from `0` to `n-1`.
*   For each employee, calculate the time it takes for the news to reach them by traversing up the management chain.
    *   Initialize `pathTime = 0` and `currentEmployee = i`.
    *   While `currentEmployee` has a manager (i.e., `manager[currentEmployee] != -1`):
        *   Move up to the manager: `currentEmployee = manager[currentEmployee]`.
        *   Add the manager's `informTime` to the `pathTime`: `pathTime += informTime[currentEmployee]`.
*   After the inner loop, `pathTime` holds the total time for the news to reach the initial employee `i`.
*   Update the overall maximum time: `maxTime = Math.max(maxTime, pathTime)`.
*   After iterating through all employees, return `maxTime`.

## Top-Down Depth-First Search (DFS)
This approach models the problem as finding the longest path in a tree, where the path weight is defined by the `informTime`. It uses a Depth-First Search (DFS) starting from the head of the company. This is a much more efficient method as it avoids redundant calculations.
**Time:** O(N). We visit each employee once to build the adjacency list (O(N)) and once during the DFS traversal (O(N)). · **Space:** O(N). The adjacency list requires O(N) space. The recursion stack for DFS can go up to a depth of H (the tree height), which is O(N) in the worst case of a skewed tree.
**Pros:** Optimal time complexity of O(N).; Each employee (node) is processed only once, avoiding redundant work.; It's an intuitive mapping of the problem to a classic tree traversal algorithm.
**Cons:** Requires O(N) extra space to store the adjacency list.; Deep recursion on a skewed tree could potentially lead to a `StackOverflowError` for extremely large N, though unlikely with the given constraints.
### Explanation
First, we need to represent the company hierarchy as a tree. An adjacency list is a suitable data structure for this, where `adj[i]` stores a list of all direct subordinates of employee `i`. We can build this list by iterating through the `manager` array once. Then, we define a recursive DFS function, say `dfs(managerID)`. This function will compute the time it takes for the news to propagate from `managerID` to all employees in their subtree. The base case for the recursion is an employee who has no subordinates (a leaf in the tree). For them, the time required is 0. For a manager `u`, the total time for their branch is their own `informTime[u]` plus the maximum time required for any of their direct subordinates' branches. The recursive step is: `time(u) = informTime[u] + max(dfs(v))` for all subordinates `v` of `u`. We initiate the process by calling `dfs(headID)`. This approach traverses each node and edge of the tree exactly once, making it very efficient.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        List<List<Integer>> adj = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int i = 0; i < n; i++) {
            if (manager[i] != -1) {
                adj.get(manager[i]).add(i);
            }
        }
        
        return dfs(headID, adj, informTime);
    }

    private int dfs(int managerID, List<List<Integer>> adj, int[] informTime) {
        if (adj.get(managerID).isEmpty()) {
            return 0;
        }

        int maxSubordinateTime = 0;
        for (int subordinate : adj.get(managerID)) {
            maxSubordinateTime = Math.max(maxSubordinateTime, dfs(subordinate, adj, informTime));
        }

        return informTime[managerID] + maxSubordinateTime;
    }
}
```
### Algorithm
*   First, build an adjacency list representation of the tree from the `manager` array. For each manager, the list will contain all their direct subordinates.
*   Define a recursive function, `dfs(managerID)`.
*   **Base Case:** If `managerID` has no subordinates (a leaf node), return 0.
*   **Recursive Step:**
    *   Initialize `maxSubordinateTime = 0`.
    *   For each `subordinate` of `managerID`:
        *   Recursively call `dfs(subordinate)` and update `maxSubordinateTime = Math.max(maxSubordinateTime, dfs(subordinate))`.
    *   The total time for the subtree rooted at `managerID` is `informTime[managerID] + maxSubordinateTime`. Return this value.
*   The final answer is the result of calling `dfs(headID)`.

## Breadth-First Search (BFS)
An alternative optimal approach using Breadth-First Search (BFS). Instead of recursion, this iterative approach explores the employee hierarchy level by level, starting from the head. It keeps track of the cumulative time taken for the news to reach each employee.
**Time:** O(N). Building the adjacency list takes O(N). The BFS traversal visits each node and edge once, which is also O(N). · **Space:** O(N). The adjacency list takes O(N) space. The queue can store up to the maximum number of nodes at any level of the tree (the tree's width), which can be O(N) in the worst case (e.g., a star graph).
**Pros:** Optimal O(N) time complexity.; Iterative approach, which avoids potential stack overflow issues from deep recursion.; Processes each employee exactly once.
**Cons:** Requires O(N) extra space for both the adjacency list and the queue.
### Explanation
Similar to the DFS approach, we first build an adjacency list to represent the tree. We use a queue to perform the BFS, which will store pairs of `(employeeID, timeToReach)`. We initialize the queue by adding the head of the company: `queue.add(new int[]{headID, 0})`. The time to reach the head is 0. We also maintain a variable `maxTime` to keep track of the maximum time encountered so far. The BFS proceeds by dequeuing an employee `u` and their `timeToReach`, updating `maxTime`, and then enqueuing all of `u`'s subordinates with their calculated arrival time (`timeToReach + informTime[u]`). After the BFS completes, `maxTime` will hold the time the last employee gets the news, which is the answer.

```java
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        List<List<Integer>> adj = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int i = 0; i < n; i++) {
            if (manager[i] != -1) {
                adj.get(manager[i]).add(i);
            }
        }

        Queue<int[]> queue = new LinkedList<>();
        // Queue stores {employeeID, timeToReachThisEmployee}
        queue.offer(new int[]{headID, 0});
        
        int maxTime = 0;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int u = current[0];
            int timeU = current[1];

            maxTime = Math.max(maxTime, timeU);

            int timeForSubordinates = timeU + informTime[u];
            for (int v : adj.get(u)) {
                queue.offer(new int[]{v, timeForSubordinates});
            }
        }
        return maxTime;
    }
}
```
### Algorithm
*   Build an adjacency list `adj` from the `manager` array.
*   Initialize a queue and add a pair `(headID, 0)`, representing `(employeeID, timeToReach)`.
*   Initialize `maxTime = 0`.
*   While the queue is not empty:
    *   Dequeue the current employee `u` and their arrival time `timeU`.
    *   Update the overall maximum time: `maxTime = Math.max(maxTime, timeU)`.
    *   Calculate the arrival time for direct subordinates: `timeForSubordinates = timeU + informTime[u]`.
    *   For each subordinate `v` of `u`:
        *   Enqueue the pair `(v, timeForSubordinates)`.
*   After the loop finishes, return `maxTime`.

# Solutions
### CSharp

```csharp
public class Solution {
    private List < int > [] g;
    private int[] informTime;
    public int NumOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        g = new List < int > [n];
        for (int i = 0; i < n; ++i) {
            g[i] = new List < int > ();
        }
        this.informTime = informTime;
        for (int i = 0; i < n; ++i) {
            if (manager[i] != -1) {
                g[manager[i]].Add(i);
            }
        }
        return dfs(headID);
    }
    private int dfs(int i) {
        int ans = 0;
        foreach(int j in g[i]) {
            ans = Math.Max(ans, dfs(j) + informTime[i]);
        }
        return ans;
    }
}
```

### Java

```java
class Solution {
private
  List<Integer>[] g;
private
  int[] informTime;
public
  int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
    g = new List[n];
    Arrays.setAll(g, k->new ArrayList<>());
    this.informTime = informTime;
    for (int i = 0; i < n; ++i) {
      if (manager[i] >= 0) {
        g[manager[i]].add(i);
      }
    }
    return dfs(headID);
  }
private
  int dfs(int i) {
    int ans = 0;
    for (int j : g[i]) {
      ans = Math.max(ans, dfs(j) + informTime[i]);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numOfMinutes(int n, int headID, vector<int> &manager,
                   vector<int> &informTime) {
    vector<vector<int>> g(n);
    for (int i = 0; i < n; ++i) {
      if (manager[i] >= 0) {
        g[manager[i]].push_back(i);
      }
    }
    function<int(int)> dfs = [&](int i) -> int {
      int ans = 0;
      for (int j : g[i]) {
        ans = max(ans, dfs(j) + informTime[i]);
      }
      return ans;
    };
    return dfs(headID);
  }
};

```

### Python

```python
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int: def dfs(i: int) -> int: ans = 0 for j in g[i]: ans = max(ans, dfs(j) + informTime[i]) return ans g = defaultdict(list) for i, x in enumerate(manager): g[x]. append(i) return dfs(headID)

```