Problem Breakdown
We are given a hierarchical organization represented as a tree where each node is an employee, headID is the root, and manager[i] defines the parent of employee i. The goal is to calculate how long it takes for news to reach every single employee. Information flows from manager to subordinates sequentially along any branch but simultaneously across different branches (parallel processing).
Key Inputs:
n: Number of employees ( to ).headID: The root node ID.manager: Array where index is employee and value is their manager (-1 for head).informTime: Time taken by an employee to inform all direct subordinates.
Key Insight:
Since information spreads in parallel across different branches, the total time required is determined solely by the “slowest” path from the root (headID) down to any leaf node (an employee with no subordinates). We need to find the maximum weighted distance from the root to any other node.
Constraints & Edge Cases:
- up to : Requires an efficient solution (), ruling out naive traversals per employee.
- Skewed trees (line graph): Depth can be large, potentially causing stack overflow in recursive solutions without configuration changes. An iterative approach is safer for a “Senior Engineer” profile.
- : The head has no subordinates; time should return 0 immediately.
Intuition
A brute-force solution might try to simulate the process minute-by-minute or traverse from every employee up to find their manager, which leads to redundant work and potentially complexity if not careful with memoization.
The core realization is that this problem maps directly to finding the longest weighted path in a tree. Since manager gives us parent pointers (edges directed towards root), we first need to invert this into an adjacency list where each node points to its children for traversal starting from headID.
Once we have the graph structure, traversing it allows us to accumulate time along paths. Because branches operate in parallel, if one branch takes 10 minutes and another takes 5, the company is fully informed when the last person (in the 10-minute branch) receives the news. Thus, we simply need the maximum accumulated informTime encountered on any path from root to leaf during a traversal.
Approach
- Graph Construction: Convert the parent-pointer array (
manager) into an adjacency list where each key is an employee ID and values are lists of their direct subordinates (children). This allows us to traverse downwards fromheadID. - Traversal Setup: Initialize a stack for Depth-First Search (DFS) or Queue for Breadth-First Search (BFS). We’ll use DFS with a list as the stack. Each element in our traversal state will track
(current_employee_id, current_accumulated_time). - State Tracking: Start by pushing
headIDonto the stack. Note that we don’t add time for the head initially because they start knowing immediately at . However, when moving to a child, we must add the parent’sinformTimeto the accumulated path sum. - DFS Execution: While traversing:
- Pop an employee and their current arrival time.
- For each subordinate (child), calculate the new arrival time (
current_time + parent_inform_time). - Push children onto stack with this new time.
- Update a global
max_timevariable whenever we push or process a node, as that represents when an employee knows the news.
- Result: The value of
max_timeafter traversal completes is our answer.
Complexity Analysis
- Time Complexity: . We iterate through each edge exactly once to build the adjacency list and traverse it exactly once during DFS/BFS. Building the graph takes linear time, as does the traversal.
- Space Complexity: . The adjacency list stores every employee ID at least once (total edges = ). The stack/queue in our traversal can grow up to proportional to the tree height or width, bounded by .
Solution
import sys
# Increase recursion depth just in case we were using recursive DFS,
# though iterative approach below avoids this. Included for completeness context.
sys.setrecursionlimit(2000)
class Solution:
def numOfMinutes(self, n: int, headID: int, manager: list[int], informTime: list[int]) -> int:
# Build adjacency list (children map) from parent pointers
children = [[] for _ in range(n)]
for i, m in enumerate(manager):
if m != -1: # Skip head's manager which is -1
children[m].append(i)
max_time = 0
# Stack stores tuples of (employee_id, time_to_reach_employee)
stack = [(headID, 0)]
while stack:
emp_idx, current_time = stack.pop()
# Update global maximum with the time this employee knows the news.
# Note: The head starts knowing at t=0 (current_time).
# Subordinates know after parent's informTime is added.
if current_time > max_time:
max_time = current_time
# Traverse to subordinates
for subordinate in children[emp_idx]:
# Time taken for subordinate to learn includes the time spent by this manager (parent)
new_time = current_time + informTime[emp_idx]
# Optimization: If a node has no subordinates, we don't need to push it
# if its informTime is 0. But pushing doesn't hurt logic.
# We only care about max time reached at any point in the tree path.
stack.append((subordinate, new_time))
return max_time
Edge Cases Handled
- Single Employee (): The loop runs once for
headID. No children exist.max_timeremains 0 (initialized). Correctly returns 0 as per Example 1. - Skewed Tree: In a line graph where every employee informs one subordinate, the depth equals . An iterative stack-based DFS handles this without hitting Python’s default recursion limit (), unlike recursive solutions which would crash on deep trees unless
sys.setrecursionlimitis used. - Parallel Branches: The algorithm naturally computes path sums for all branches and tracks the maximum, correctly handling parallel processing where different subordinates learn at different times but we wait for the last one (max).
- Leaf Nodes with 0 Inform Time: Employees without subordinates have
informTime[i] == 0. When pushed to stack as children of a parent, they inherit the accumulated time. Since they don’t push further nodes, their path ends there. The max is updated correctly based on when they received the news (which depends on ancestors’ times).