Time Needed to Inform All Employees

Medium
461.

Time Needed to Inform All Employees

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.

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 <= 40
  • 0 <= headID < n
  • manager[headID] == -1 and the structure is a tree.
  • 0 <= informTime[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number} headID
 * @param {number[]} manager
 * @param {number[]} informTime
 * @return {number}
 */
var numOfMinutes = function(n, headID, manager, informTime) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 40
  • 0 <= headID < n
  • manager[headID] == -1 and the structure is a tree.
  • 0 <= informTime[i] <= 1000

Hints for Time Needed to Inform All Employees

  1. Hint 1

    Invert manager into a children list so you can walk down the hierarchy.

  2. Hint 2

    Depth-first search from the head, carrying the elapsed time on the path so far.

  3. 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

  1. Build children[m] for each employee.
  2. Stack (node, elapsed) from (head, 0); push each child with elapsed + informTime[node].
  3. 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 best

Java

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)