DSA problem

Time Needed to Inform All Employees

MediumDepth First Search (DFS)Pattern: Depth First Search (DFS)top300AmazonMicrosoftGoogleLinkedInBloomberg

A company has n employees with a unique ID for each employee from 0 to n - 1. The head of the company has the ID headID. Each employee has one direct manager given in manager, where manager[i] is the direct manager of the i-th employee (manager[headID] = -1). Also, it is guaranteed that the subordination relationships form a tree. The head of the company wants to inform all employees of an urgent piece of news, and needs informTime[i] minutes to inform all of their direct subordinates. Return the number of minutes needed to inform all employees of the news.

This is a tree problem in disguise: the relationships form a rooted tree at headID. The total time to inform a subtree is informTime[root] + max(time to inform each child subtree), because the manager triggers all direct subordinates in parallel after informTime[root] minutes — the slowest subordinate chain determines the overall delay.

To compute this efficiently, first invert the manager array into a children-list (an adjacency list from each manager to their direct reports). Then run a DFS from headID returning the time needed for that node's subtree. The recurrence is naturally time(node) = informTime[node] + max(time(child)) for child in children[node], with leaves contributing informTime[leaf] = 0 (since leaves have no subordinates).

The algorithm visits each node and edge exactly once, costing O(n) time and O(n) space for the children adjacency list and recursion stack. This is asymptotically optimal — every employee must at least be considered.

Examples

Example 1

Input: n = 1, headID = 0, manager = [-1], informTime = [0]

Output: 0

Explanation: A single employee has no subordinates; nothing to inform, so the time is 0.

Example 2

Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]

Output: 1

Explanation: Employee 2 is the head and takes 1 minute to inform all 5 direct subordinates in parallel.

Example 3

Input: n = 7, headID = 6, manager = [1,2,3,4,5,6,-1], informTime = [0,6,5,4,3,2,1]

Output: 21

Explanation: The chain 6->5->4->3->2->1->0 accumulates 1+2+3+4+5+6 = 21 minutes.

Constraints

1 <= n <= 10^5
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.

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

dfstreegraphrecursion

Browse all DSA problems