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 <= 1050 <= headID < nmanager.length == n0 <= manager[i] < nmanager[headID] == -1informTime.length == n0 <= informTime[i] <= 1000informTime[i] == 0 if employee i has no subordinates.We can think of the employee-manager structure as a tree. The head of the company is the root, and each employee is a node whose parent is the manager. Our goal is to determine the maximum time required to inform all employees. We can perform a Depth-First Search (DFS) starting from the headID to explore all paths and calculate the time required for each path.
The solution employs a Depth-First Search (DFS) starting from the headID. The recursive DFS function calculates the maximum time required by iterating through all the subordinates.
Java
Time Complexity: O(n). Each node is visited exactly once.
Space Complexity: O(n). The recursion stack can go up to the depth of the tree, which in the worst case can be n.
We use a Breadth-First Search (BFS) approach to explore the company hierarchy level by level. We maintain a queue to propagate the information and calculate the total time as we move through each level of subordinates.
The C# solution uses a queue to implement the BFS traversal. Each element in the queue represents an employee and the total time taken to inform this employee. The function iteratively processes the employees until all are informed.
JavaScript
Time Complexity: O(n) because each employee is processed exactly once.
Space Complexity: O(n) due to the space required to store the subordinate map and the queue.
| Approach | Complexity |
|---|---|
| DFS Approach | Time Complexity: O(n). Each node is visited exactly once. |
| BFS Approach | Time Complexity: O(n) because each employee is processed exactly once. |
Time Needed to Inform All Employees - Leetcode 1376 - Python • NeetCodeIO • 12,877 views views
Watch 9 more video solutions →Practice Time Needed to Inform All Employees with our built-in code editor and test cases.
Practice on FleetCode