LeetCode 1376 - Time Needed to Inform All Employees

The problem asks us to calculate the total time it takes for a piece of urgent information to propagate through a compan

leetcodemediumtreedepth-first-searchbreadth-first-search

LeetCode Problem 1376

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Breadth-First Search

Solution

Problem Understanding

The problem asks us to calculate the total time it takes for a piece of urgent information to propagate through a company hierarchy, starting from the head of the company. Each employee has a direct manager, forming a tree structure rooted at the head of the company. The manager array specifies the direct manager for each employee, with manager[headID] = -1 indicating the root. Each employee also has an associated informTime representing how long it takes that employee to inform all their direct subordinates.

The input consists of: n, the number of employees; headID, the unique ID of the company's head; manager, an array where manager[i] is the direct manager of employee i; and informTime, an array where informTime[i] is the time employee i takes to inform their subordinates. The output is a single integer representing the total time for the message to reach all employees.

Constraints indicate that n can be up to 10^5, which rules out inefficient solutions that traverse each node excessively. The informTime can be zero if an employee has no subordinates. The input guarantees all employees are reachable from the head, so we do not need to handle disconnected nodes. Important edge cases include a single employee (n = 1) or all employees having zero informTime.

Approaches

A brute-force approach would simulate the propagation recursively or iteratively, starting from the head. For each employee, we would add the employee's informTime to the total time of reaching their subordinates. This works correctly but may be inefficient if implemented poorly because repeated calculations could occur if you traverse nodes multiple times without caching or proper tree traversal.

The optimal approach leverages the tree structure. First, build an adjacency list mapping each manager to their direct subordinates. Then, perform a Depth-First Search (DFS) or Breadth-First Search (BFS) starting from the head, accumulating the time to reach each node. DFS is particularly convenient because the longest path from the root to a leaf determines the total inform time. BFS can also be used, maintaining a queue of (employeeID, accumulatedTime) pairs.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Recursive propagation without precomputing subordinates can revisit nodes multiple times.
Optimal O(n) O(n) Build adjacency list and perform DFS/BFS to propagate time; each node visited once.

Algorithm Walkthrough

  1. Create an empty adjacency list tree mapping each manager to their direct subordinates.
  2. Iterate over the manager array. For each employee i, if manager[i] != -1, append i to tree[manager[i]].
  3. Define a DFS function dfs(employeeID) that returns the total time needed to inform all subordinates of employeeID.
  4. For each subordinate in tree[employeeID], recursively call dfs(subordinate) and keep track of the maximum returned time.
  5. Return the sum of the current employee's informTime[employeeID] and the maximum time among subordinates.
  6. Call dfs(headID) to compute the total time needed for all employees to be informed.

Why it works: This works because the total time is determined by the longest path from the head to any leaf employee. DFS ensures that all paths are evaluated, and by taking the maximum at each step, we capture the critical path for information propagation.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        tree = defaultdict(list)
        for employeeID, mgr in enumerate(manager):
            if mgr != -1:
                tree[mgr].append(employeeID)
        
        def dfs(empID: int) -> int:
            if empID not in tree:
                return 0
            max_sub_time = 0
            for sub in tree[empID]:
                max_sub_time = max(max_sub_time, dfs(sub))
            return informTime[empID] + max_sub_time
        
        return dfs(headID)

This Python solution first constructs a tree dictionary where each manager maps to their list of direct subordinates. The dfs function recursively computes the maximum time required to inform all subordinates. For leaf employees, dfs returns 0, effectively handling the base case. The solution then returns the total time starting from headID.

Go Solution

package main

func numOfMinutes(n int, headID int, manager []int, informTime []int) int {
    tree := make(map[int][]int)
    for empID, mgr := range manager {
        if mgr != -1 {
            tree[mgr] = append(tree[mgr], empID)
        }
    }
    
    var dfs func(int) int
    dfs = func(empID int) int {
        maxSubTime := 0
        for _, sub := range tree[empID] {
            if subTime := dfs(sub); subTime > maxSubTime {
                maxSubTime = subTime
            }
        }
        return informTime[empID] + maxSubTime
    }
    
    return dfs(headID)
}

In Go, we use a map[int][]int to represent the adjacency list. The recursive dfs function computes the maximum time among subordinates, similar to the Python version. The implementation avoids explicit nil checks because range over an empty slice is safe in Go.

Worked Examples

Example 1:

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

The head has no subordinates. The DFS returns 0 immediately. Output is 0.

Example 2:

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

The adjacency list is {2: [0,1,3,4,5]}. DFS for head 2 computes max of DFS(0), DFS(1), DFS(3), DFS(4), DFS(5), all of which return 0. Adding informTime[2] = 1, the total is 1.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each employee is visited exactly once during DFS.
Space O(n) The adjacency list and recursion stack may each store up to n elements.

Because each employee is processed only once and we only store the tree structure and recursion stack, the solution is efficient for large n up to 10^5.

Test Cases

# Basic single employee
assert Solution().numOfMinutes(1, 0, [-1], [0]) == 0

# Head informs all others
assert Solution().numOfMinutes(6, 2, [2,2,-1,2,2,2], [0,0,1,0,0,0]) == 1

# Chain of command
assert Solution().numOfMinutes(4, 0, [-1,0,1,2], [1,2,3,4]) == 10  # 1+2+3+4

# Multiple levels with zero times
assert Solution().numOfMinutes(5, 0, [-1,0,0,1,1], [0,0,0,0,0]) == 0

# Large balanced tree
n = 7
manager = [-1,0,0,1,1,2,2]
informTime = [1,2,3,4,5,6,7]
assert Solution().numOfMinutes(n, 0, manager, informTime) == 1+2+5  # Longest path: 0->1->4
Test Why
Single employee Ensures base case handled correctly
Head informs all Tests fan-out from head
Chain of command Tests cumulative time along a long path
Zero inform times Tests leaf-only employees
Balanced tree Tests selection of the longest path in a multi-level tree

Edge Cases

One edge case is when n = 1. The solution must correctly return 0 without attempting any recursive calls or accesses beyond the head employee. A second edge case occurs when some employees have informTime = 0, representing leaves. The DFS base case ensures these nodes return 0. A third edge case is a deeply nested hierarchy, such as a single chain of length n, which could stress recursion depth. Both Python and Go solutions handle this because the recursion stack grows linearly with the depth, which is acceptable within typical stack limits for n ≤ 10^5.