Time Needed to Inform All Employees

Medium Graphs BFS / DFS Basics Original on LeetCode

Reported atAdobeMedia.net

Time Needed to Inform All Employees is a medium graphs problem solved with the bfs / dfs basics pattern. The best approach, optimal (dfs down the tree from the head), runs in O(n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (walk up from every employee) up.

Problem

A company has n employees numbered 0 to n - 1. Employee headID is the head, and every other employee i has a direct manager manager[i] (the head has manager[headID] == -1). Together these links form a tree.

The head wants to share urgent news. An employee i who knows the news needs informTime[i] minutes to pass it to all of their direct reports at once; those reports then start passing it on to their own reports.

Return the number of minutes until every employee has heard the news.

Examples

Example 1

Input
n = 6, headID = 0, manager = [-1, 0, 0, 1, 1, 2], informTime = [2, 5, 1, 0, 0, 0]
Output
7
Why
Employee 0 needs 2 minutes to reach 1 and 2; employee 1 then needs 5 more to reach 3 and 4, so the last people hear at minute 7.

Example 2

Input
n = 4, headID = 2, manager = [2, 2, -1, 0], informTime = [3, 0, 4, 0]
Output
7
Why
The news goes 2 -> 0 (4 minutes) and then 0 -> 3 (3 more minutes). Employee 1 already knew at minute 4.

Example 3

Input
n = 1, headID = 0, manager = [-1], informTime = [0]
Output
0
Why
The head is the only employee, so nobody needs to be told.

Constraints

  • 1 <= n <= 10^5
  • 0 <= headID < n
  • manager.length == informTime.length == n
  • manager[headID] == -1; for every other employee 0 <= manager[i] < n
  • 0 <= informTime[i] <= 1000, and informTime[i] == 0 when employee i has no direct reports
  • Every employee is connected to the head through the manager links (the links form a tree).

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (walk up from every employee)O(n · h)O(1)
Optimal (DFS down the tree from the head)O(n)O(n)

1Brute force (walk up from every employee)

TimeO(n · h)Each of the n employees walks up at most h levels, where h can be n in a chain.
SpaceO(1)Only a few counters.

For each employee, follow manager links up to the head and add up the informTime of every manager passed. The answer is the largest total.

  1. For each employee i, set total = 0 and cur = manager[i].
  2. While cur != -1, add informTime[cur] to total and move cur = manager[cur].
  3. Keep the maximum total.
class Solution {
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        int best = 0;
        for (int i = 0; i < n; i++) {
            int total = 0;
            int cur = manager[i];
            while (cur != -1) {
                total += informTime[cur];
                cur = manager[cur];
            }
            best = Math.max(best, total);
        }
        return best;
    }
}

2Optimal (DFS down the tree from the head)

TimeO(n)Every employee is pushed and popped exactly once.
SpaceO(n)The children lists and the stack hold O(n) entries.

Turn manager into a children list, then traverse the tree once from the head, carrying the time at which each employee hears the news. A child hears at time(parent) + informTime[parent]. The answer is the largest time seen. An explicit stack avoids recursion depth problems on a long chain.

  1. Build children[m] for every manager m.
  2. Push (headID, 0) on a stack.
  3. Pop (u, t): update the answer with t, then push (v, t + informTime[u]) for every child v of u.
  4. Return the answer once the stack is empty.
class Solution {
    public 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[] top = stack.pop();
            int u = top[0], t = top[1];
            best = Math.max(best, t);
            for (int v : children.get(u)) {
                stack.push(new int[] { v, t + informTime[u] });
            }
        }
        return best;
    }
}

Edge cases to test

  • Only the head exists: the answer is 0
  • A single long chain: the times add up along the whole chain
  • A flat company where everyone reports to the head: the answer is informTime[headID]
  • A deep branch with small times can beat a shallow branch with a large time

Hints

Hint 1

The time at which employee i hears the news is the sum of informTime over all managers above i.

Hint 2

The answer is the largest such sum over all employees, the longest weighted root-to-leaf path.

Hint 3

Build a children list from manager[] and walk down from the head once, carrying the time so far.

FAQ

What is the best time complexity for Time Needed to Inform All Employees?

Optimal (DFS down the tree from the head) runs in O(n) time and O(n) extra space. Every employee is pushed and popped exactly once.

Which pattern does Time Needed to Inform All Employees use?

It is a graphs problem that uses the bfs / dfs basics pattern. Other problems with the same pattern: BFS - Normal + Level by Level, DFS - Recursive + Iterative, Clone Graph.

Is there a brute force solution for Time Needed to Inform All Employees?

Yes. Brute force (walk up from every employee) takes O(n · h) time and O(1) space. For each employee, follow manager links up to the head and add up the informTime of every manager passed.

Which edge cases should I test for Time Needed to Inform All Employees?

Only the head exists: the answer is 0; A single long chain: the times add up along the whole chain; A flat company where everyone reports to the head: the answer is informTime[headID]; A deep branch with small times can beat a shallow branch with a large time.