Skip to main content
Talentd

Employee Importance - Solution & Explanation

MediumArrayHash TableTreeDepth-First Search16 min readAsked at: Amazon, Microsoft, Uber +3
Practice this problem

Problem Statement

You have a data structure of employee information, including the employee's unique ID, importance value, and direct subordinates' IDs.

You are given an array of employees employees where:

  • employees[i].id is the ID of the ith employee.
  • employees[i].importance is the importance value of the ith employee.
  • employees[i].subordinates is a list of the IDs of the direct subordinates of the ith employee.

Given an integer id that represents an employee's ID, return the total importance value of this employee and all their direct and indirect subordinates.

 

Example 1:

Input: employees = [[1,5,[2,3]],[2,3,[]],[3,3,[]]], id = 1
Output: 11
Explanation: Employee 1 has an importance value of 5 and has two direct subordinates: employee 2 and employee 3.
They both have an importance value of 3.
Thus, the total importance value of employee 1 is 5 + 3 + 3 = 11.

Example 2:

Input: employees = [[1,2,[5]],[5,-3,[]]], id = 5
Output: -3
Explanation: Employee 5 has an importance value of -3 and has no direct subordinates.
Thus, the total importance value of employee 5 is -3.

 

Constraints:

  • 1 <= employees.length <= 2000
  • 1 <= employees[i].id <= 2000
  • All employees[i].id are unique.
  • -100 <= employees[i].importance <= 100
  • One employee has at most one direct leader and may have several subordinates.
  • The IDs in employees[i].subordinates are valid IDs.

Approach Overview

Problem Overview: You’re given a list of employees where each employee has an id, an importance value, and a list of direct subordinates. The task is to compute the total importance for a given employee, including the importance of all direct and indirect subordinates in the hierarchy.

The structure naturally forms a management tree. Each employee points to their children (subordinates). The main challenge is quickly locating employees by ID and traversing the hierarchy without repeatedly scanning the entire array.

Approach 1: Depth-First Search (DFS) using Recursion (Time: O(n), Space: O(n))

First build a hash map that maps employee id to the corresponding employee object. This allows constant-time lookup when you need to find a subordinate. Starting from the target employee ID, perform a recursive depth-first search through all subordinates. For each employee visited, add their importance and recursively process each subordinate ID.

The key insight: every employee is visited exactly once. The recursion naturally follows the management hierarchy, which behaves like a tree. Time complexity is O(n) because each employee is processed once. Space complexity is O(n) due to the hash map and recursion stack in the worst case. This approach directly applies concepts from Depth-First Search and Hash Table usage.

Approach 2: Breadth-First Search (BFS) using Queue (Time: O(n), Space: O(n))

The same preprocessing step applies: build a map from employee ID to employee object. Instead of recursion, use a queue to perform a breadth-first traversal of the hierarchy. Start by pushing the target employee ID into the queue. While the queue is not empty, pop an employee, add their importance to the total, and push all their subordinates into the queue.

This approach processes employees level by level in the management hierarchy. Each employee still gets visited exactly once, so the time complexity remains O(n). The queue can hold up to all employees in the worst case, giving O(n) space complexity. BFS is often preferred if you want to avoid recursion depth issues or when working iteratively. It demonstrates standard Breadth-First Search traversal on a tree-like hierarchy.

Recommended for interviews: Both DFS and BFS solutions are optimal with O(n) time. Interviewers typically expect the DFS solution because it maps directly to the recursive structure of the hierarchy. Showing the hash map optimization is critical; without it, repeated scans of the employee list would degrade performance. Implementing either DFS or BFS cleanly demonstrates strong understanding of graph/tree traversal.

Approach 1: Depth-First Search (DFS) using Recursion

The problem can be approached by using a Depth-First Search (DFS). The main idea is to accumulate the importance of an employee and all of their direct and indirect subordinates. We use a recursive function to traverse the subordinates of each employee. The base case is when an employee has no subordinates (leaf node). Each recursion step accumulates importance from the current employee and proceeds to accumulate from its subordinates.

This Python solution defines a recursive dfs function that fetches an employee from a map (created for fast lookup) and calculates their total importance including their subordinates recursively.

Code

PythonC++JavaC#JavaScript

Python

C++

Java

C#

JavaScript

Complexity

Time Complexity: O(N), where N is the number of employees, as each employee is visited once.
Space Complexity: O(N), due to the recursion stack and storage in the map for employees.

Try this approach in the editor →

Approach 2: Breadth-First Search (BFS) using Queue

An alternative method involves using Breadth-First Search (BFS). In this approach, a queue is used to iteratively explore each level of employee hierarchy starting from the given employee ID. One processes each employee by summing their importance and enqueuing their subordinates. This technique assures visiting all employees in a breadth-wise manner and eventually collecting the cumulative importance value.

This Python code uses a BFS approach. We employ a queue where we enqueue employees as we visit them and total their importance. Every dequeued employee adds their importance to the result and their subordinates to the queue.

Code

PythonC++JavaC#JavaScript

Python

C++

Java

C#

JavaScript

Complexity

Time Complexity: O(N), as it processes each employee once.
Space Complexity: O(N), due to the queue and employee mapping storage.

Try this approach in the editor →

Approach 3: Hash Table + DFS

We use a hash table d to store all employee information, where the key is the employee's ID, and the value is the employee object. Then we start a depth-first search from the given employee ID. Each time we traverse to an employee, we add the employee's importance to the answer, and recursively traverse all the subordinates of the employee, adding the importance of the subordinates to the answer as well.

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

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Depth-First Search (DFS) using Recursion

Time Complexity: O(N), where N is the number of employees, as each employee is visited once.
Space Complexity: O(N), due to the recursion stack and storage in the map for employees.

Breadth-First Search (BFS) using Queue

Time Complexity: O(N), as it processes each employee once.
Space Complexity: O(N), due to the queue and employee mapping storage.

Hash Table + DFS—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS using Recursion + Hash MapO(n)O(n)Most common interview solution. Clean recursive traversal of the hierarchy.
BFS using Queue + Hash MapO(n)O(n)Preferred when avoiding recursion or when iterative traversal is required.

Video Solution

花花酱 LeetCode 690. Employee Importance - 刷题找工作 EP75 • Hua Hua • 3,181 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Employee Importance easy or hard?
Employee Importance is considered a medium-level problem. The core idea is simple once you recognize the hierarchy as a tree, but candidates must combine hash maps with DFS or BFS traversal to achieve the optimal O(n) solution.
Employee Importance Python/Java solution
In Python and Java, the common solution builds a map from employee ID to employee object, then runs DFS or BFS to sum importance values. The algorithm runs in O(n) time and O(n) space and is straightforward to implement in both languages using dictionaries/maps and recursion or queues.
How to solve Employee Importance in O(n)?
Build a hash map from employee ID to the employee object so subordinate lookups are constant time. Start from the target employee and traverse all subordinates using DFS recursion or a BFS queue. Accumulate importance values while visiting each employee once, resulting in O(n) time.
What is the best approach for Employee Importance?
The optimal approach uses a hash map combined with DFS or BFS traversal. First map employee IDs to employee objects for O(1) lookup. Then traverse the hierarchy starting from the given employee ID and sum the importance values of all reachable subordinates. Both DFS and BFS achieve O(n) time complexity.
Is Employee Importance asked at Google/Amazon/Meta?
Hierarchy traversal problems like Employee Importance appear frequently in interviews at companies such as Amazon, Google, and Meta. They test understanding of tree or graph traversal, hash maps, and recursion or queue-based BFS techniques.
What data structure is used in Employee Importance?
The main data structures are a hash map for fast employee lookup and either a recursion stack (DFS) or queue (BFS) for traversal. The employee relationships form a tree-like hierarchy where each node represents an employee and edges represent management relationships.
What is the time complexity of Employee Importance?
The time complexity is O(n), where n is the number of employees. Each employee is visited exactly once during the DFS or BFS traversal. Building the ID-to-employee hash map also takes O(n) time, keeping the total complexity linear.

Ready to solve this problem?

Practice Employee Importance with our built-in code editor and test cases.

Practice on FleetCode
Previous

Nested List Weight Sum