1376. Time Needed to Inform All Employees - Explanation

Problem Link



Intuition

The company structure forms a tree with the head of the company as the root. Each manager must inform their direct subordinates, who then inform their subordinates, and so on. The total time to inform everyone equals the longest path from the root to any leaf, where each edge weight is the manager's inform time.

We can traverse this tree using dfs, tracking the accumulated time as we go deeper. At each node, we add that manager's inform time before visiting their subordinates. The answer is the maximum time across all leaf nodes.

Algorithm

  1. Build an adjacency list representing the manager-subordinate relationships.
  2. Start dfs from the head of the company.
  3. For each node, recursively compute the time to inform all employees in its subtree.
  4. The time at each node is informTime[node] plus the maximum time from all its children.
  5. Return the maximum time found from the root.
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        adj = [[] for _ in range(n)]
        for i in range(n):
            if i != headID:
                adj[manager[i]].append(i)

        def dfs(node):
            res = 0
            for child in adj[node]:
                res = max(res, informTime[node] + dfs(child))
            return res

        return dfs(headID)

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

Intuition

Instead of using recursion, we can traverse the tree level by level using bfs. We process nodes in waves, tracking the time at which each employee receives the news. The maximum time across all employees gives us the answer.

Each node in the queue stores both the employee ID and the time at which they were informed. When we process a node, we inform all their direct reports, adding the manager's inform time to compute when each subordinate receives the news.

Algorithm

  1. Build an adjacency list from the manager array.
  2. Initialize a queue with the head employee and time 0.
  3. Track the maximum time seen so far.
  4. For each node dequeued, update the maximum time and enqueue all subordinates with their accumulated time.
  5. A subordinate's time equals their manager's time plus the manager's inform time.
  6. Return the maximum time after processing all employees.
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        adj = defaultdict(list)
        for i in range(n):
            adj[manager[i]].append(i)

        q = deque([(headID, 0)])  # (id, time)
        res = 0

        while q:
            node, time = q.popleft()
            res = max(res, time)
            for emp in adj[node]:
                q.append((emp, time + informTime[node]))

        return res

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

3. Topological Sort (Kahn's Algorithm)

Intuition

We can reverse our thinking: instead of propagating time down from the root, we can compute times bottom-up starting from leaf employees. Leaf employees have an indegree of 0 (no one reports to them). They propagate their total time upward to their managers.

A manager's total time is the maximum among all their subordinates' times plus their own inform time. We process employees in topological order, from leaves toward the root. When all of a manager's subordinates have been processed, we can compute and propagate the manager's time.

Algorithm

  1. Compute the indegree of each employee (how many people report to them).
  2. Initialize a queue with all leaf employees (indegree = 0).
  3. For each employee processed, add their inform time to their accumulated time.
  4. Propagate this time to their manager, taking the maximum if the manager has multiple subordinates.
  5. Decrement the manager's indegree; if it becomes 0, add them to the queue.
  6. Return the time at the head of the company.
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        indegree = [0] * n
        time = [0] * n

        for i in range(n):
            if manager[i] != -1:
                indegree[manager[i]] += 1

        queue = deque()
        for i in range(n):
            if indegree[i] == 0:
                queue.append(i)

        while queue:
            node = queue.popleft()
            time[node] += informTime[node]
            if manager[node] != -1:
                time[manager[node]] = max(time[manager[node]], time[node])
                indegree[manager[node]] -= 1
                if indegree[manager[node]] == 0:
                    queue.append(manager[node])

        return time[headID]

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

4. Depth First Search (Optimal)

Intuition

Instead of building an explicit adjacency list, we can traverse from each employee up to the root, caching results along the way. For any employee, their total inform time is their own inform time plus their manager's total inform time.

We use the manager array directly for traversal and cache computed results in the inform time array itself. Once an employee's path to root is computed, we mark their manager as -1 to indicate completion. This approach uses path compression similar to Union-Find.

Algorithm

  1. For each employee, recursively compute their total time by following the manager chain to the root.
  2. Base case: if an employee has no manager (-1), return their inform time.
  3. Add the manager's total time to the current employee's inform time.
  4. Mark the employee's manager as -1 to cache the result and prevent recomputation.
  5. Track the maximum inform time seen across all employees.
  6. Return the maximum time.
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        def dfs(node):
            if manager[node] != -1:
                informTime[node] += dfs(manager[node])
                manager[node] = -1
            return informTime[node]

        res = 0
        for node in range(n):
            res = max(res, dfs(node))
        return res

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n) for recursion stack.

Common Pitfalls

Summing Instead of Taking Maximum Over Children

The total time is the longest path from root to any leaf, not the sum of all inform times. When a manager informs multiple subordinates, they are informed simultaneously. You should take the maximum time among all subtrees, not add them together. Using sum instead of max produces answers that are way too large.

Forgetting That Leaf Nodes Have Zero Inform Time

Employees with no subordinates (leaf nodes) have informTime[i] = 0. When building the adjacency list or computing times, ensure you handle this correctly. Some solutions mistakenly add inform time even for leaves or skip leaves entirely, leading to incorrect results.

Not Building the Adjacency List Correctly

The manager array gives parent pointers, but for DFS/BFS you need children pointers. A common mistake is iterating incorrectly when building the adjacency list or accidentally including the head in some manager's list. The head has manager[headID] = -1, so you must skip adding edges for the head node.