Skip to main content
Talentd

Time Needed to Inform All Employees - Solution & Explanation

MediumTreeDepth-First SearchBreadth-First Search12 min readAsked at: Amazon, Microsoft, Infosys +2
Practice this problem

Problem Statement

A company has n employees with a unique ID for each employee from 0 to n - 1. The head of the company is the one with headID.

Each employee has one direct manager given in the manager array where manager[i] is the direct manager of the i-th employee, manager[headID] = -1. Also, it is guaranteed that the subordination relationships have a tree structure.

The head of the company wants to inform all the company employees of an urgent piece of news. He will inform his direct subordinates, and they will inform their subordinates, and so on until all employees know about the urgent news.

The i-th employee needs informTime[i] minutes to inform all of his direct subordinates (i.e., After informTime[i] minutes, all his direct subordinates can start spreading the news).

Return the number of minutes needed to inform all the employees about the urgent news.

 

Example 1:

Input: n = 1, headID = 0, manager = [-1], informTime = [0]
Output: 0
Explanation: The head of the company is the only employee in the company.

Example 2:

Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
Output: 1
Explanation: The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all.
The tree structure of the employees in the company is shown.

 

Constraints:

  • 1 <= n <= 105
  • 0 <= headID < n
  • manager.length == n
  • 0 <= manager[i] < n
  • manager[headID] == -1
  • informTime.length == n
  • 0 <= informTime[i] <= 1000
  • informTime[i] == 0 if employee i has no subordinates.
  • It is guaranteed that all the employees can be informed.

Approach Overview

Problem Overview: A company has n employees with a hierarchical manager structure forming a tree. The head starts an announcement, and each manager takes informTime[i] minutes to pass the message to their direct subordinates. The goal is to compute the total time required for the information to reach every employee.

The manager array defines a parent-child relationship, which naturally forms a tree. The head of the company is the root, and every employee is a node. Solving the problem means computing the longest time taken along any path from the head to a leaf employee.

Approach 1: Depth-First Search (DFS) Traversal (O(n) time, O(n) space)

Build an adjacency list where each manager maps to their direct subordinates. Start a DFS from the head employee and propagate accumulated time down the hierarchy. Each recursive call adds the current manager's informTime to the running total before visiting children.

The key insight: the overall time equals the maximum time taken along any root-to-leaf path in the management tree. DFS naturally explores one branch fully before moving to the next, making it easy to track the longest propagation time. Use recursion or an explicit stack to traverse the tree. The traversal touches each employee exactly once, giving O(n) time complexity and O(n) space for the adjacency list and recursion stack.

This approach works well when you're comfortable modeling hierarchical relationships as trees and computing path-based metrics. DFS keeps the implementation compact and maps directly to the recursive structure of the organization chart.

Approach 2: Breadth-First Search (BFS) Level Traversal (O(n) time, O(n) space)

Another way to model the spread of information is level-by-level propagation using Breadth-First Search. Construct the same adjacency list of manager → subordinates, then push the head into a queue with time 0. Each time you process an employee, enqueue all direct subordinates with accumulated time currentTime + informTime[current].

Track the maximum time encountered during traversal. BFS simulates how information spreads outward through the company hierarchy. Each employee is visited once, and queue operations are constant time, resulting in O(n) time complexity and O(n) space for the queue and adjacency list.

BFS is particularly intuitive when you think of the message spreading simultaneously across different branches of the organization. The queue explicitly tracks the propagation frontier.

Recommended for interviews: The DFS solution is typically expected. It directly models the problem as finding the longest path from the head in a tree and produces a clean recursive implementation using Depth-First Search. BFS is equally efficient and shows that you understand message propagation simulations. Demonstrating both approaches signals strong command of tree traversal patterns.

Approach 1: DFS Approach

We can think of the employee-manager structure as a tree. The head of the company is the root, and each employee is a node whose parent is the manager. Our goal is to determine the maximum time required to inform all employees. We can perform a Depth-First Search (DFS) starting from the headID to explore all paths and calculate the time required for each path.

The solution employs a Depth-First Search (DFS) starting from the headID. The recursive DFS function calculates the maximum time required by iterating through all the subordinates.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n). Each node is visited exactly once.
Space Complexity: O(n). The recursion stack can go up to the depth of the tree, which in the worst case can be n.

Try this approach in the editor →

Approach 2: BFS Approach

We use a Breadth-First Search (BFS) approach to explore the company hierarchy level by level. We maintain a queue to propagate the information and calculate the total time as we move through each level of subordinates.

The C# solution uses a queue to implement the BFS traversal. Each element in the queue represents an employee and the total time taken to inform this employee. The function iteratively processes the employees until all are informed.

Code

C#JavaScript

C#

JavaScript

Complexity

Time Complexity: O(n) because each employee is processed exactly once.
Space Complexity: O(n) due to the space required to store the subordinate map and the queue.

Try this approach in the editor →

Approach 3: DFS

We first build an adjacent list g according to the manager array, where g[i] represents all direct subordinates of employee i.

Next, we design a function dfs(i), which means the time required for employee i to notify all his subordinates (including direct subordinates and indirect subordinates), and then the answer is dfs(headID).

In function dfs(i), we need to traverse all direct subordinates j of i. For each subordinate, employee i needs to notify him, which takes informTime[i] time, and his subordinates need to notify their subordinates, which takes dfs(j) time. We take the maximum value of informTime[i] + dfs(j) as the return value of function dfs(i).

The time complexity is O(n), and the space complexity is O(n). Where n is the number of employees.

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
DFS Approach

Time Complexity: O(n). Each node is visited exactly once.
Space Complexity: O(n). The recursion stack can go up to the depth of the tree, which in the worst case can be n.

BFS Approach

Time Complexity: O(n) because each employee is processed exactly once.
Space Complexity: O(n) due to the space required to store the subordinate map and the queue.

DFS—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Depth-First Search (DFS)O(n)O(n)Best when modeling hierarchy as a tree and computing maximum root-to-leaf propagation time.
Breadth-First Search (BFS)O(n)O(n)Useful when simulating message spread level-by-level across the organization.

Video Solution

Time Needed to Inform All Employees - Leetcode 1376 - Python • NeetCodeIO • 14,635 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Time Needed to Inform All Employees easy or hard?
The problem is rated Medium because it requires recognizing that the manager array forms a tree and then applying DFS or BFS traversal. The implementation itself is straightforward once the tree representation is built, but identifying the longest propagation path is the key step.
Time Needed to Inform All Employees Python/Java solution
Python and Java implementations usually build an adjacency list using a dictionary or ArrayList. A DFS function recursively visits each subordinate while accumulating the total time, updating a global or returned maximum. The algorithm processes each node once, producing an O(n) solution.
How to solve Time Needed to Inform All Employees in O(n)?
Build a graph where each manager stores a list of direct subordinates. Start traversal from the head employee and accumulate the time taken along the path. Track the maximum time encountered while visiting nodes using DFS or BFS. Since every employee is processed once, the overall complexity remains O(n).
What is the best approach for Time Needed to Inform All Employees?
Depth-First Search on the management tree is the most common approach. Convert the manager array into an adjacency list of manager to subordinates, then compute the longest time from the head to any employee. This runs in O(n) time because each employee is visited exactly once.
Is Time Needed to Inform All Employees asked at Google/Amazon/Meta?
This problem represents a common interview pattern involving tree traversal and propagation through hierarchies. Variations of this problem appear in interviews at companies like Amazon, Google, and Meta where candidates must model organizational structures as trees and compute longest propagation paths.
What data structure is used in Time Needed to Inform All Employees?
The main data structure is an adjacency list representing a tree or directed graph from manager to subordinates. Traversal is then performed using either a recursion stack for DFS or a queue for BFS to propagate the information through the hierarchy.
What is the time complexity of Time Needed to Inform All Employees?
Both DFS and BFS solutions run in O(n) time where n is the number of employees. Each node in the management tree is processed once while propagating the inform time. The space complexity is also O(n) due to the adjacency list and recursion stack or queue.

Ready to solve this problem?

Practice Time Needed to Inform All Employees with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Maximum Path Sum

Next

Maximum Depth of Binary Tree