NeetCode #440LC-1376MediumTrees
← Back to All Problems#440 · #1376 · Time Needed to Inform All Employees(通知所有员工所需的时间)
📌 Problem Statement & Constraints
A company has
n employees with a unique head, given by headID and the manager array. Each manager takes informTime[i] minutes to inform their direct reports, who then inform theirs in parallel. Return the total minutes needed to inform all employees. Constraints: 1 <= n <= 10^5, 0 <= headID < n; the manager relation forms a tree.💡 Core Algorithmic Approaches
- The structure is a tree rooted at
headID, with edges from manager to report. - The time for a node's subtree is
informTime[node] + max(time of each child's subtree), since the children are informed in parallel. - So a post-order DFS returning the subtree time gives the answer at the root.
- The manager array must be inverted into a children adjacency list first.
💻 Benchmark Python3 Implementation
class Solution:
def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
from collections import defaultdict
children = defaultdict(list)
for i, m in enumerate(manager):
if m != -1:
children[m].append(i) # invert manager -> reports
def dfs(node: int) -> int:
if not children[node]:
return 0 # a leaf takes no time to inform others
# children are informed in parallel -> take the maximum
return informTime[node] + max(dfs(c) for c in children[node])
return dfs(headID)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each node is visited once.
💾 Space Complexity
O(n) for the adjacency list plus O(h) for the recursion.
⚠️ Interview Pitfalls & Follow-ups
- Summing the children's times instead of taking the maximum: the informing happens in parallel, so the longest branch determines the total.
- Forgetting the leaf case: a leaf returns 0, not
informTime[leaf](which is 0 anyway, but the guard makes it explicit). - Building the adjacency list in the wrong direction: the edges go from manager to report.
- Handling the head's manager being -1: the
if m != -1guard is required.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.