Time Needed to Inform All Employees
Medium · Graphs · Tree · Depth-First Search · Breadth-First Search
Problem
A company has n employees with IDs 0 to n - 1; the head of the company has ID headID. manager[i] is the direct manager of employee i, and manager[headID] = -1. The reporting lines always form a tree.
The head wants to spread urgent news. An employee i who has the news needs informTime[i] minutes to pass it to all of their direct reports at once, who then pass it on the same way. Return the number of minutes until every employee has heard the news.
Examples
Input: n = 5, headID = 0, manager = [-1,0,0,1,1], informTime = [3,4,0,0,0] Output: 7
The head spends 3 minutes informing 1 and 2, then employee 1 spends 4 more minutes informing 3 and 4: 7 minutes.
Input: n = 1, headID = 0, manager = [-1], informTime = [0] Output: 0
The head is the only employee, so nobody needs to be told.
Input: n = 4, headID = 2, manager = [2,2,-1,0], informTime = [5,0,1,0] Output: 6
The head (1 minute) informs 0 and 1; employee 0 (5 minutes) informs 3, at minute 6.
Constraints
- 1 <= n <= 10^5
- 0 <= headID < n
- len(manager) == len(informTime) == n
- manager[headID] == -1, and 0 <= manager[i] < n otherwise
- 0 <= informTime[i] <= 1000, and informTime[i] == 0 if employee i has no reports
- Every employee can be reached from the head
Approaches
- Baseline: climb from every employee — time O(n · depth), space O(1)
Follow-up
With n up to 10^5 the reporting tree can be a single chain 10^5 deep. A recursive DFS would hit Python's recursion limit there; the queue (or an explicit stack) does not. Could you also solve it in O(n) with no children lists at all, by memoizing each employee's minute while climbing manager?
Related problems
Start free on Cariara · Coding problems · System design studio
