⚡Flashcard Drill➔
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

  1. The structure is a tree rooted at headID, with edges from manager to report.
  2. The time for a node's subtree is informTime[node] + max(time of each child's subtree), since the children are informed in parallel.
  3. So a post-order DFS returning the subtree time gives the answer at the root.
  4. 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 != -1 guard is required.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems