1376. Time Needed to Inform All Employees - Explanation

Description

A company has n employees labeled from 0 to n - 1, and employee headID is the head. The head knows some news at time 0. Every other employee has one direct manager given by manager[i]; the head has manager -1. These relationships form a tree.

Once employee i receives the news, all of their direct reports receive it after informTime[i] minutes. Different employees can spread the news at the same time. Return the time when every employee knows the news.

Employees with no direct reports have an inform time of 0. The arrays are indexed by employee ID, and the head can have any ID.

Each edge is labeled with the time its manager takes to inform a direct report.

Example 1:

Time Needed to Inform All Employees, example 1: illustration of the example

Input: n = 5
headID = 0
manager = [-1,0,0,1,1]
informTime = [2,3,0,0,0]

Output: 5

Explanation: Employee 0 informs employees 1 and 2 after 2 minutes. Employee 1 then takes 3 more minutes to inform employees 3 and 4. Everyone knows the news after 5 minutes.

Example 2:

Time Needed to Inform All Employees, example 2: illustration of the example

Input: n = 4
headID = 2
manager = [2,0,-1,2]
informTime = [4,0,1,0]

Output: 5

Explanation: Head 2 informs employees 0 and 3 after 1 minute. Employee 0 then informs employee 1 after 4 more minutes, so the total is 5 minutes.

Example 3:

Time Needed to Inform All Employees, example 3: illustration of the example

Input: n = 3
headID = 1
manager = [1,-1,1]
informTime = [0,0,0]

Output: 0

Explanation: Head 1 has an inform time of 0, so both direct reports learn the news immediately. No time is needed.

Constraints:

1 <= n <= 100000
0 <= headID < n
manager.length == informTime.length == n
manager[headID] == -1; every other manager is an employee ID from 0 to n - 1.
Manager relationships form one rooted tree with head headID.
0 <= informTime[i] <= 1000
Employees without direct reports have informTime[i] == 0.

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Tree/Graph Data Structures - Understanding how to represent hierarchical relationships using adjacency lists
Depth First Search (DFS) - Recursively traversing tree structures and tracking accumulated values along paths
Breadth First Search (BFS) - Level-by-level traversal using queues to process nodes
Topological Sort - Processing nodes in dependency order, particularly Kahn's algorithm using indegrees

1. Depth First Search

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

Build an adjacency list representing the manager-subordinate relationships.
Start dfs from the head of the company.
For each node, recursively compute the time to inform all employees in its subtree.
The time at each node is informTime[node] plus the maximum time from all its children.
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)

public class Solution {
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        List<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++) {
            if (i != headID) {
                adj[manager[i]].add(i);
            }
        }

        return dfs(headID, adj, informTime);
    }

    private int dfs(int node, List<Integer>[] adj, int[] informTime) {
        int res = 0;
        for (int child : adj[node]) {
            res = Math.max(res, informTime[node] + dfs(child, adj, informTime));
        }
        return res;
    }
}

class Solution {
public:
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        vector<vector<int>> adj(n);
        for (int i = 0; i < n; i++) {
            if (i != headID) {
                adj[manager[i]].push_back(i);
            }
        }
        return dfs(headID, adj, informTime);
    }

private:
    int dfs(int node, vector<vector<int>>& adj, vector<int>& informTime) {
        int res = 0;
        for (int child : adj[node]) {
            res = max(res, informTime[node] + dfs(child, adj, informTime));
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number} n
     * @param {number} headID
     * @param {number[]} manager
     * @param {number[]} informTime
     * @return {number}
     */
    numOfMinutes(n, headID, manager, informTime) {
        const adj = Array.from({ length: n }, () => []);
        for (let i = 0; i < n; i++) {
            if (i !== headID) {
                adj[manager[i]].push(i);
            }
        }

        const dfs = (node) => {
            let res = 0;
            for (const child of adj[node]) {
                res = Math.max(res, informTime[node] + dfs(child));
            }
            return res;
        };

        return dfs(headID);
    }
}

func numOfMinutes(n int, headID int, manager []int, informTime []int) int {
    adj := make([][]int, n)
    for i := range adj {
        adj[i] = []int{}
    }
    for i := 0; i < n; i++ {
        if i != headID {
            adj[manager[i]] = append(adj[manager[i]], i)
        }
    }

    var dfs func(node int) int
    dfs = func(node int) int {
        res := 0
        for _, child := range adj[node] {
            res = max(res, informTime[node]+dfs(child))
        }
        return res
    }

    return dfs(headID)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

class Solution {
    fun numOfMinutes(n: Int, headID: Int, manager: IntArray, informTime: IntArray): Int {
        val adj = Array(n) { mutableListOf<Int>() }
        for (i in 0 until n) {
            if (i != headID) {
                adj[manager[i]].add(i)
            }
        }

        fun dfs(node: Int): Int {
            var res = 0
            for (child in adj[node]) {
                res = maxOf(res, informTime[node] + dfs(child))
            }
            return res
        }

        return dfs(headID)
    }
}

impl Solution {
    pub fn num_of_minutes(n: i32, head_id: i32, manager: Vec<i32>, inform_time: Vec<i32>) -> i32 {
        let n = n as usize;
        let head = head_id as usize;
        let mut adj = vec![vec![]; n];
        for i in 0..n {
            if i != head {
                adj[manager[i] as usize].push(i);
            }
        }

        fn dfs(node: usize, adj: &[Vec<usize>], inform_time: &[i32]) -> i32 {
            let mut res = 0;
            for &child in &adj[node] {
                res = res.max(inform_time[node] + dfs(child, adj, inform_time));
            }
            res
        }

        dfs(head, &adj, &inform_time)
    }
}

Time & Space Complexity

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

2. Breadth First Search

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

Build an adjacency list from the manager array.
Initialize a queue with the head employee and time 0.
Track the maximum time seen so far.
For each node dequeued, update the maximum time and enqueue all subordinates with their accumulated time.
A subordinate's time equals their manager's time plus the manager's inform time.
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

public class Solution {
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        Map<Integer, List<Integer>> adj = new HashMap<>();
        for (int i = 0; i < n; i++) {
            adj.computeIfAbsent(manager[i], k -> new ArrayList<>()).add(i);
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{headID, 0});
        int res = 0;

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int id = curr[0], time = curr[1];
            res = Math.max(res, time);
            for (int emp : adj.getOrDefault(id, new ArrayList<>())) {
                queue.add(new int[]{emp, time + informTime[id]});
            }
        }

        return res;
    }
}

class Solution {
public:
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        unordered_map<int, vector<int>> adj;
        for (int i = 0; i < n; ++i) {
            adj[manager[i]].push_back(i);
        }

        queue<pair<int, int>> q; // {id, time}
        q.push({headID, 0});
        int res = 0;

        while (!q.empty()) {
            auto [id, time] = q.front();
            q.pop();
            res = max(res, time);
            for (int emp : adj[id]) {
                q.push({emp, time + informTime[id]});
            }
        }

        return res;
    }
};

class Solution {
    /**
     * @param {number} n
     * @param {number} headID
     * @param {number[]} manager
     * @param {number[]} informTime
     * @return {number}
     */
    numOfMinutes(n, headID, manager, informTime) {
        const adj = new Map();
        for (let i = 0; i < n; i++) {
            if (!adj.has(manager[i])) adj.set(manager[i], []);
            adj.get(manager[i]).push(i);
        }

        const queue = new Queue([[headID, 0]]); // [id, time]
        let res = 0;

        while (!queue.isEmpty()) {
            const [id, time] = queue.pop();
            res = Math.max(res, time);
            if (adj.has(id)) {
                for (const emp of adj.get(id)) {
                    queue.push([emp, time + informTime[id]]);
                }
            }
        }

        return res;
    }
}

func numOfMinutes(n int, headID int, manager []int, informTime []int) int {
    adj := make(map[int][]int)
    for i := 0; i < n; i++ {
        adj[manager[i]] = append(adj[manager[i]], i)
    }

    queue := [][2]int{{headID, 0}} // {id, time}
    res := 0

    for len(queue) > 0 {
        curr := queue[0]
        queue = queue[1:]
        id, time := curr[0], curr[1]
        if time > res {
            res = time
        }
        for _, emp := range adj[id] {
            queue = append(queue, [2]int{emp, time + informTime[id]})
        }
    }

    return res
}

class Solution {
    fun numOfMinutes(n: Int, headID: Int, manager: IntArray, informTime: IntArray): Int {
        val adj = mutableMapOf<Int, MutableList<Int>>()
        for (i in 0 until n) {
            adj.getOrPut(manager[i]) { mutableListOf() }.add(i)
        }

        val queue: Queue<Pair<Int, Int>> = LinkedList()
        queue.add(Pair(headID, 0))
        var res = 0

        while (queue.isNotEmpty()) {
            val (id, time) = queue.poll()
            res = maxOf(res, time)
            adj[id]?.forEach { emp ->
                queue.add(Pair(emp, time + informTime[id]))
            }
        }

        return res
    }
}

class Solution {
    func numOfMinutes(_ n: Int, _ headID: Int, _ manager: [Int], _ informTime: [Int]) -> Int {
        var adj = [Int: [Int]]()
        for i in 0..<n {
            adj[manager[i], default: []].append(i)
        }

        var queue = [(headID, 0)] // (id, time)
        var res = 0

        while !queue.isEmpty {
            let (id, time) = queue.removeFirst()
            res = max(res, time)
            if let employees = adj[id] {
                for emp in employees {
                    queue.append((emp, time + informTime[id]))
                }
            }
        }

        return res
    }
}

impl Solution {
    pub fn num_of_minutes(n: i32, head_id: i32, manager: Vec<i32>, inform_time: Vec<i32>) -> i32 {
        let n = n as usize;
        let mut adj: HashMap<i32, Vec<usize>> = HashMap::new();
        for i in 0..n {
            adj.entry(manager[i]).or_default().push(i);
        }

        let mut queue = VecDeque::new();
        queue.push_back((head_id as usize, 0i32));
        let mut res = 0;

        while let Some((id, time)) = queue.pop_front() {
            res = res.max(time);
            if let Some(emps) = adj.get(&(id as i32)) {
                for &emp in emps {
                    queue.push_back((emp, time + inform_time[id]));
                }
            }
        }

        res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $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

Compute the indegree of each employee (how many people report to them).
Initialize a queue with all leaf employees (indegree = 0).
For each employee processed, add their inform time to their accumulated time.
Propagate this time to their manager, taking the maximum if the manager has multiple subordinates.
Decrement the manager's indegree; if it becomes 0, add them to the queue.
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]

public class Solution {
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        int[] indegree = new int[n];
        int[] time = new int[n];

        for (int i = 0; i < n; i++) {
            if (manager[i] != -1) {
                indegree[manager[i]]++;
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                queue.add(i);
            }
        }

        while (!queue.isEmpty()) {
            int node = queue.poll();
            time[node] += informTime[node];
            if (manager[node] != -1) {
                time[manager[node]] = Math.max(time[manager[node]], time[node]);
                indegree[manager[node]]--;
                if (indegree[manager[node]] == 0) {
                    queue.add(manager[node]);
                }
            }
        }

        return time[headID];
    }
}

class Solution {
public:
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        vector<int> indegree(n, 0);
        vector<int> time(n, 0);

        for (int i = 0; i < n; ++i) {
            if (manager[i] != -1) {
                indegree[manager[i]]++;
            }
        }

        queue<int> queue;
        for (int i = 0; i < n; ++i) {
            if (indegree[i] == 0) {
                queue.push(i);
            }
        }

        while (!queue.empty()) {
            int node = queue.front();
            queue.pop();
            time[node] += informTime[node];
            if (manager[node] != -1) {
                time[manager[node]] = max(time[manager[node]], time[node]);
                indegree[manager[node]]--;
                if (indegree[manager[node]] == 0) {
                    queue.push(manager[node]);
                }
            }
        }

        return time[headID];
    }
};

class Solution {
    /**
     * @param {number} n
     * @param {number} headID
     * @param {number[]} manager
     * @param {number[]} informTime
     * @return {number}
     */
    numOfMinutes(n, headID, manager, informTime) {
        const indegree = Array(n).fill(0);
        const time = Array(n).fill(0);

        for (let i = 0; i < n; i++) {
            if (manager[i] !== -1) {
                indegree[manager[i]]++;
            }
        }

        const queue = new Queue();
        for (let i = 0; i < n; i++) {
            if (indegree[i] === 0) {
                queue.push(i);
            }
        }

        while (!queue.isEmpty()) {
            const node = queue.pop();
            time[node] += informTime[node];
            if (manager[node] !== -1) {
                time[manager[node]] = Math.max(time[manager[node]], time[node]);
                indegree[manager[node]]--;
                if (indegree[manager[node]] === 0) {
                    queue.push(manager[node]);
                }
            }
        }

        return time[headID];
    }
}

func numOfMinutes(n int, headID int, manager []int, informTime []int) int {
    indegree := make([]int, n)
    time := make([]int, n)

    for i := 0; i < n; i++ {
        if manager[i] != -1 {
            indegree[manager[i]]++
        }
    }

    queue := []int{}
    for i := 0; i < n; i++ {
        if indegree[i] == 0 {
            queue = append(queue, i)
        }
    }

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        time[node] += informTime[node]
        if manager[node] != -1 {
            if time[node] > time[manager[node]] {
                time[manager[node]] = time[node]
            }
            indegree[manager[node]]--
            if indegree[manager[node]] == 0 {
                queue = append(queue, manager[node])
            }
        }
    }

    return time[headID]
}

class Solution {
    fun numOfMinutes(n: Int, headID: Int, manager: IntArray, informTime: IntArray): Int {
        val indegree = IntArray(n)
        val time = IntArray(n)

        for (i in 0 until n) {
            if (manager[i] != -1) {
                indegree[manager[i]]++
            }
        }

        val queue: Queue<Int> = LinkedList()
        for (i in 0 until n) {
            if (indegree[i] == 0) {
                queue.add(i)
            }
        }

        while (queue.isNotEmpty()) {
            val node = queue.poll()
            time[node] += informTime[node]
            if (manager[node] != -1) {
                time[manager[node]] = maxOf(time[manager[node]], time[node])
                indegree[manager[node]]--
                if (indegree[manager[node]] == 0) {
                    queue.add(manager[node])
                }
            }
        }

        return time[headID]
    }
}

class Solution {
    func numOfMinutes(_ n: Int, _ headID: Int, _ manager: [Int], _ informTime: [Int]) -> Int {
        var indegree = [Int](repeating: 0, count: n)
        var time = [Int](repeating: 0, count: n)

        for i in 0..<n {
            if manager[i] != -1 {
                indegree[manager[i]] += 1
            }
        }

        var queue = [Int]()
        for i in 0..<n {
            if indegree[i] == 0 {
                queue.append(i)
            }
        }

        while !queue.isEmpty {
            let node = queue.removeFirst()
            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]
    }
}

impl Solution {
    pub fn num_of_minutes(n: i32, head_id: i32, manager: Vec<i32>, inform_time: Vec<i32>) -> i32 {
        let n = n as usize;
        let mut indegree = vec![0i32; n];
        let mut time = vec![0i32; n];

        for i in 0..n {
            if manager[i] != -1 {
                indegree[manager[i] as usize] += 1;
            }
        }

        let mut queue = VecDeque::new();
        for i in 0..n {
            if indegree[i] == 0 {
                queue.push_back(i);
            }
        }

        while let Some(node) = queue.pop_front() {
            time[node] += inform_time[node];
            if manager[node] != -1 {
                let mgr = manager[node] as usize;
                time[mgr] = time[mgr].max(time[node]);
                indegree[mgr] -= 1;
                if indegree[mgr] == 0 {
                    queue.push_back(mgr);
                }
            }
        }

        time[head_id as usize]
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $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

For each employee, recursively compute their total time by following the manager chain to the root.
Base case: if an employee has no manager (-1), return their inform time.
Add the manager's total time to the current employee's inform time.
Mark the employee's manager as -1 to cache the result and prevent recomputation.
Track the maximum inform time seen across all employees.
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

public class Solution {
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        int res = 0;
        for (int node = 0; node < n; node++) {
            res = Math.max(res, dfs(node, manager, informTime));
        }
        return res;
    }

    private int dfs(int node, int[] manager, int[] informTime) {
        if (manager[node] != -1) {
            informTime[node] += dfs(manager[node], manager, informTime);
            manager[node] = -1;
        }
        return informTime[node];
    }
}

class Solution {
public:
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        function<int(int)> dfs = [&](int node) {
            if (manager[node] != -1) {
                informTime[node] += dfs(manager[node]);
                manager[node] = -1;
            }
            return informTime[node];
        };

        int res = 0;
        for (int node = 0; node < n; ++node) {
            res = max(res, dfs(node));
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number} n
     * @param {number} headID
     * @param {number[]} manager
     * @param {number[]} informTime
     * @return {number}
     */
    numOfMinutes(n, headID, manager, informTime) {
        const dfs = (node) => {
            if (manager[node] !== -1) {
                informTime[node] += dfs(manager[node]);
                manager[node] = -1;
            }
            return informTime[node];
        };

        let res = 0;
        for (let node = 0; node < n; node++) {
            res = Math.max(res, dfs(node));
        }
        return res;
    }
}

func numOfMinutes(n int, headID int, manager []int, informTime []int) int {
    var dfs func(node int) int
    dfs = func(node int) int {
        if manager[node] != -1 {
            informTime[node] += dfs(manager[node])
            manager[node] = -1
        }
        return informTime[node]
    }

    res := 0
    for node := 0; node < n; node++ {
        if val := dfs(node); val > res {
            res = val
        }
    }
    return res
}

class Solution {
    fun numOfMinutes(n: Int, headID: Int, manager: IntArray, informTime: IntArray): Int {
        fun dfs(node: Int): Int {
            if (manager[node] != -1) {
                informTime[node] += dfs(manager[node])
                manager[node] = -1
            }
            return informTime[node]
        }

        var res = 0
        for (node in 0 until n) {
            res = maxOf(res, dfs(node))
        }
        return res
    }
}

class Solution {
    func numOfMinutes(_ n: Int, _ headID: Int, _ manager: [Int], _ informTime: [Int]) -> Int {
        var manager = manager
        var informTime = informTime

        func dfs(_ node: Int) -> Int {
            if manager[node] != -1 {
                informTime[node] += dfs(manager[node])
                manager[node] = -1
            }
            return informTime[node]
        }

        var res = 0
        for node in 0..<n {
            res = max(res, dfs(node))
        }
        return res
    }
}

impl Solution {
    pub fn num_of_minutes(n: i32, _head_id: i32, manager: Vec<i32>, inform_time: Vec<i32>) -> i32 {
        let n = n as usize;
        let mut manager = manager;
        let mut inform_time = inform_time;

        fn dfs(node: usize, manager: &mut Vec<i32>, inform_time: &mut Vec<i32>) -> i32 {
            if manager[node] != -1 {
                let parent = manager[node] as usize;
                inform_time[node] += dfs(parent, manager, inform_time);
                manager[node] = -1;
            }
            inform_time[node]
        }

        let mut res = 0;
        for node in 0..n {
            res = res.max(dfs(node, &mut manager, &mut inform_time));
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $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.