1376. Time Needed to Inform All Employees LeetCode Solution

In this guide, you will get 1376. Time Needed to Inform All Employees LeetCode Solution with the best time and space complexity. The solution to Time Needed to Inform All Employees problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Time Needed to Inform All Employees solution in C++
Time Needed to Inform All Employees solution in Java
Time Needed to Inform All Employees solution in Python
Additional Resources

1376. Time Needed to Inform All Employees LeetCode Solution image

Problem Statement of Time Needed to Inform All Employees

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:

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.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

1376. Time Needed to Inform All Employees LeetCode Solution in C++

class Solution {
 public:
  int numOfMinutes(int n, int headID, vector<int>& manager,
                   vector<int>& informTime) {
    int ans = 0;

    for (int i = 0; i < n; ++i)
      ans = max(ans, dfs(i, headID, manager, informTime, {}));

    return ans;
  }

 private:
  int dfs(int i, int headID, const vector<int>& manager,
          const vector<int>& informTime, unordered_map<int, int>&& mem) {
    if (const auto it = mem.find(i); it != mem.cend())
      return it->second;
    if (i == headID)
      return 0;

    const int parent = manager[i];
    return mem[i] = informTime[parent] +
                    dfs(parent, headID, manager, informTime, std::move(mem));
  }
};
/* code provided by PROGIEZ */

1376. Time Needed to Inform All Employees LeetCode Solution in Java

class Solution {
  public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
    int ans = 0;
    Map<Integer, Integer> mem = new HashMap<>();

    for (int i = 0; i < n; ++i)
      ans = Math.max(ans, dfs(i, headID, manager, informTime, mem));

    return ans;
  }

  int dfs(int i, int headID, int[] manager, int[] informTime, Map<Integer, Integer> mem) {
    if (mem.containsKey(i))
      return mem.get(i);
    if (i == headID)
      return 0;

    final int parent = manager[i];
    mem.put(i, informTime[parent] + dfs(parent, headID, manager, informTime, mem));
    return mem.get(i);
  }
}
// code provided by PROGIEZ