Time Needed to Inform All Employees

MediumTree / Graph Traversal · DFS · BFS🧩 Graph DFS LeetCode #1376 ↗Updated Oct 30, 2026

Problem

A company of n employees forms a tree: manager[i] is the direct boss of employee i, and the head headID has manager[headID] = -1. When an employee learns some news, they need informTime[i] minutes before all of their direct reports hear it. Return how many minutes pass until every employee knows the news, starting from the head.

Inputn = 1, headID = 0, manager = [-1], informTime = [0]Output0

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

Inputn = 4, headID = 0, manager = [-1,0,1,2], informTime = [1,2,3,0]Output6

1 ≤ n ≤ 10⁵ · 0 ≤ informTime[i] ≤ 1000 · informTime[i] = 0 if i has no reports · the structure is guaranteed to be a tree rooted at headID

Try it yourself

Java

class Solution {
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The time an employee hears the news is the sum of informTime along the path from the head down to them. The answer is the longest such root-to-node path — one traversal of the tree computes every path sum.

PatternGraph DFS

Instinct Connected regions, all paths, reachability, cloning or 2-colouring a graph or grid: dive from a node, mark it, recurse into unvisited neighbours.

Memory hack Mark before you march: go deep, paint as you go, and back up only when every door is already painted.

Open the Graph DFS guide →

Approaches

Brute ForceClimb Each Employee’s Chain

Time O(n·h)Space O(1)

For every employee, follow manager[] pointers up to the head and add each boss’s informTime; that sum is the minute this employee hears the news. Take the maximum. h is the tree height, so a long chain makes it O(n²).

Java

public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
    int best = 0;
    for (int i = 0; i < n; i++) {
        int minutes = 0;
        // walk up to the head, paying each boss's delay
        for (int boss = manager[i]; boss != -1; boss = manager[boss]) {
            minutes += informTime[boss];
        }
        best = Math.max(best, minutes);
    }
    return best;
}

No extra memory, but shared upper chains are re-walked for every employee.

BetterClimb with Memoisation

Time O(n)Space O(n)

Cache reach[i] = minute employee i hears the news. When climbing, stop at the first ancestor whose value is already known, then fill in the climbed chain from the top down. Every employee is resolved exactly once.

Java

public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
    int[] reach = new int[n];          // minute i hears the news, -1 = unknown
    Arrays.fill(reach, -1);
    reach[headID] = 0;
    int[] path = new int[n];
    int best = 0;
    for (int i = 0; i < n; i++) {
        int len = 0, cur = i;
        while (reach[cur] == -1) {     // climb until a known ancestor
            path[len++] = cur;
            cur = manager[cur];
        }
        while (len > 0) {              // resolve the chain from the top down
            int e = path[--len];
            reach[e] = reach[manager[e]] + informTime[manager[e]];
        }
        best = Math.max(best, reach[i]);
    }
    return best;
}

Linear, but needs a path buffer and is less direct than a top-down sweep.

OptimalTop-Down BFS over Reports

Time O(n)Space O(n)

Turn manager[] into child lists, then sweep from the head. Each employee passes reach[boss] + informTime[boss] down to every direct report. Every node and edge is touched once, and the queue avoids deep recursion.

Java

public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
    List<List<Integer>> reports = new ArrayList<>();
    for (int i = 0; i < n; i++) reports.add(new ArrayList<>());
    for (int i = 0; i < n; i++) {
        if (manager[i] != -1) reports.get(manager[i]).add(i);
    }
    int[] reach = new int[n];
    Deque<Integer> queue = new ArrayDeque<>();
    queue.offer(headID);
    int best = 0;
    while (!queue.isEmpty()) {
        int boss = queue.poll();
        best = Math.max(best, reach[boss]);
        for (int e : reports.get(boss)) {
            reach[e] = reach[boss] + informTime[boss];
            queue.offer(e);
        }
    }
    return best;
}

Single clean traversal, iterative — safe even for a 10⁵-long chain.

Pro tip

A recursive DFS returning informTime[u] + max(dfs(child)) is equally short, but mention the stack-depth risk on a chain of 10⁵ employees.

At a glance

Level	Approach	Time	Space
Brute Force	Climb Each Employee’s Chain	`O(n·h)`	`O(1)`
Better	Climb with Memoisation	`O(n)`	`O(n)`
Optimal	Top-Down BFS over Reports	`O(n)`	`O(n)`

Common pitfalls

Summing all informTime values — siblings are told in parallel, so only one path counts.
Adding the employee’s own informTime instead of their manager’s when computing reach.
Deep recursion on a straight chain — can overflow the stack at n = 10⁵.

Interview tips

Rephrase it as “maximum weighted root-to-leaf path” — it clicks immediately.
Mention the parent-pointer climb first, then show why shared prefixes make it quadratic.
Point out the input is a parent array: building child lists is the one-time O(n) setup.

Pattern

Tree DFS/BFS with path accumulation → a value flows from the root and each node adds its edge cost.

My notes saved in this browser