Time Needed to Inform All Employees — Problem & Solution
Time Needed to Inform All Employees solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Time Needed to Inform All Employees is a medium coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Breadth-First Search, Trees
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A company has n employees with unique ids 0 through n - 1. The head has id headID, and manager[i] is the direct manager of employee i (the head's entry is -1). Employee i needs informTime[i] minutes to pass news to all of their direct subordinates, who then start informing theirs.
Return the number of minutes until every employee has been informed.
Example 1
Input: n = 1, headID = 0, manager = [-1], informTime = [0]
Output: 0
Example 2
Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
Output: 1
Example 3
Input: n = 4, headID = 2, manager = [3,3,-1,2], informTime = [0,0,162,914]
Output: 1076
Constraints
1 <= n <= 400 <= headID < nmanager[headID] == -1 and the structure is a tree.0 <= informTime[i] <= 1000
Hints for Time Needed to Inform All Employees
Hint 1
Invert
managerinto a children list so you can walk down the hierarchy.Hint 2
Depth-first search from the head, carrying the elapsed time on the path so far.
Hint 3
The answer is the largest elapsed time reached at any employee.
How to solve Time Needed to Inform All Employees
Invert manager into a children list and DFS from the head accumulating time down each path; the answer is the deepest accumulated time.
Approach
- Build
children[m]for each employee. - Stack
(node, elapsed)from(head, 0); push each child withelapsed + informTime[node]. - Track the maximum
elapsed.
Why it works
Everyone at a level is informed in parallel, so the time to reach an employee is the sum of inform times along the management chain, and the last one informed determines the total.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Leaf employees have
informTime = 0; the maximum is still taken at them.
Reference solution
Python
def numOfMinutes(n: int, headID: int, manager, informTime) -> int:
children = [[] for _ in range(n)]
for i in range(n):
if manager[i] != -1:
children[manager[i]].append(i)
best = 0
stack = [(headID, 0)]
while stack:
node, elapsed = stack.pop()
best = max(best, elapsed)
for child in children[node]:
stack.append((child, elapsed + informTime[node]))
return bestJava
public static int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
List<List<Integer>> children = new ArrayList<>();
for (int i = 0; i < n; i++) children.add(new ArrayList<>());
for (int i = 0; i < n; i++) {
if (manager[i] != -1) children.get(manager[i]).add(i);
}
int best = 0;
Deque<int[]> stack = new ArrayDeque<>();
stack.push(new int[]{headID, 0});
while (!stack.isEmpty()) {
int[] entry = stack.pop();
best = Math.max(best, entry[1]);
for (int child : children.get(entry[0])) {
stack.push(new int[]{child, entry[1] + informTime[entry[0]]});
}
}
return best;
}C++
int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
vector<vector<int>> children(n);
for (int i = 0; i < n; i++) {
if (manager[i] != -1) children[manager[i]].push_back(i);
}
int best = 0;
vector<pair<int,int>> stack;
stack.push_back(make_pair(headID, 0));
while (!stack.empty()) {
pair<int,int> entry = stack.back();
stack.pop_back();
best = max(best, entry.second);
for (int child : children[entry.first]) {
stack.push_back(make_pair(child, entry.second + informTime[entry.first]));
}
}
return best;
}JavaScript
var numOfMinutes = function(n, headID, manager, informTime) {
const children = [];
for (let i = 0; i < n; i++) children.push([]);
for (let i = 0; i < n; i++) {
if (manager[i] !== -1) children[manager[i]].push(i);
}
let best = 0;
const stack = [[headID, 0]];
while (stack.length > 0) {
const entry = stack.pop();
const node = entry[0], elapsed = entry[1];
if (elapsed > best) best = elapsed;
for (let i = 0; i < children[node].length; i++) {
stack.push([children[node][i], elapsed + informTime[node]]);
}
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)