Employee Importance solution and explanation
Google
9 more videos on this problem
花花酱 LeetCode 690. Employee Importance - 刷题找工作 EP75Hua Hua · 5:19 · 3K views
employee importance | employee importance leetcode | tree bfs | leetcode 690Naresh Gupta · 7:47 · 2K views
Leetcode 690 - Graph, BFS | Employee ImportanceNideesh Terapalli · 6:22 · 2K views
Google Coding Interview Question | Leetcode 690 | Employee ImportanceWorkWithGoogler · 8:03 · 1K views
LEETCODE 690 EMPLOYEE IMPORTANCE PYTHON | DFSSasa codes · 8:30 · 519 views
690. Employee Importance - English VersionSimple Code - 단순코드 · 6:04 · 490 views
Leetcode-690. Employee Importance | Google Interview Question| C++ | Easy ExplanationNayema Laboni · 12:49 · 442 views
Leetcode 690 Employee Importance - LAYOFF ALGORITHM??TheAnalyticGuy · 3:10 · 352 views
Leetcode 690 Employee Importance - Uber Interview Question Solved Using BFS & Queue In JavaAlgorithmicIQ · 12:46 · 313 views
Leetcode | 690. Employee Importance | PythonParth Mathuria · 10:41 · 230 views
The problem
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].idis the ID of theithemployee.employees[i].importanceis the importance value of theithemployee.employees[i].subordinatesis a list of the IDs of the direct subordinates of theithemployee.
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 <= 20001 <= employees[i].id <= 2000- All
employees[i].idare unique. -100 <= employees[i].importance <= 100- One employee has at most one direct leader and may have several subordinates.
- The IDs in
employees[i].subordinatesare 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.
class Employee:
def __init__(self, id: int, importance: int, subordinates: list):
self.id = id
self.importance = importance
self.subordinates = subordinates
class Solution:
def getImportance(self, employees: list, id: int) -> int:
employee_map = {e.id: e for e in employees}
def dfs(emp_id: int) -> int:
employee = employee_map[emp_id]
return employee.importance + sum(dfs(sub_id) for sub_id in employee.subordinates)
return dfs(id)import java.util.*;
class Employee {
public int id;
public int importance;
public List<Integer> subordinates;
}
class Solution {
public int getImportance(List<Employee> employees, int id) {
Map<Integer, Employee> employeeMap = new HashMap<>();
for (Employee e : employees) {
employeeMap.put(e.id, e);
}
return dfs(employeeMap, id);
}
private int dfs(Map<Integer, Employee> map, int id) {
Employee employee = map.get(id);
int total_importance = employee.importance;
for (int sub_id : employee.subordinates) {
total_importance += dfs(map, sub_id);
}
return total_importance;
}
}#include <vector>
#include <unordered_map>
using namespace std;
struct Employee {
int id;
int importance;
vector<int> subordinates;
};
class Solution {
public:
int getImportance(vector<Employee*> employees, int id) {
unordered_map<int, Employee*> employee_map;
for (auto e : employees) {
employee_map[e->id] = e;
}
return dfs(employee_map, id);
}
private:
int dfs(unordered_map<int, Employee*>& map, int id) {
Employee* employee = map[id];
int total_importance = employee->importance;
for (int sub_id : employee->subordinates) {
total_importance += dfs(map, sub_id);
}
return total_importance;
}
};function getImportance(employees, id) {
const employeeMap = new Map();
for (const e of employees) {
employeeMap.set(e.id, e);
}
function dfs(empId) {
const employee = employeeMap.get(empId);
let totalImportance = employee.importance;
for (const subId of employee.subordinates) {
totalImportance += dfs(subId);
}
return totalImportance;
}
return dfs(id);
}using System.Collections.Generic;
class Employee {
public int id;
public int importance;
public IList<int> subordinates;
}
class Solution {
public int GetImportance(IList<Employee> employees, int id) {
var employeeMap = new Dictionary<int, Employee>();
foreach (var e in employees) {
employeeMap[e.id] = e;
}
return DFS(employeeMap, id);
}
private int DFS(Dictionary<int, Employee> map, int id) {
var employee = map[id];
int totalImportance = employee.importance;
foreach (var subId in employee.subordinates) {
totalImportance += DFS(map, subId);
}
return totalImportance;
}
}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.
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.
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.
class Employee:
def __init__(self, id: int, importance: int, subordinates: list):
self.id = id
self.importance = importance
self.subordinates = subordinates
class Solution:
def getImportance(self, employees: list, id: int) -> int:
employee_map = {e.id: e for e in employees}
queue = [id]
total_importance = 0
while queue:
current_id = queue.pop(0)
employee = employee_map[current_id]
total_importance += employee.importance
queue.extend(employee.subordinates)
return total_importanceimport java.util.*;
class Employee {
public int id;
public int importance;
public List<Integer> subordinates;
}
class Solution {
public int getImportance(List<Employee> employees, int id) {
Map<Integer, Employee> employeeMap = new HashMap<>();
for (Employee e : employees) {
employeeMap.put(e.id, e);
}
Queue<Integer> queue = new LinkedList<>();
queue.add(id);
int total_importance = 0;
while (!queue.isEmpty()) {
int current_id = queue.poll();
Employee employee = employeeMap.get(current_id);
total_importance += employee.importance;
queue.addAll(employee.subordinates);
}
return total_importance;
}
}#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;
struct Employee {
int id;
int importance;
vector<int> subordinates;
};
class Solution {
public:
int getImportance(vector<Employee*> employees, int id) {
unordered_map<int, Employee*> employee_map;
for (auto e : employees) {
employee_map[e->id] = e;
}
queue<int> q;
q.push(id);
int total_importance = 0;
while (!q.empty()) {
int current_id = q.front();
q.pop();
Employee* employee = employee_map[current_id];
total_importance += employee->importance;
for (int sub_id : employee->subordinates) {
q.push(sub_id);
}
}
return total_importance;
}
};function getImportance(employees, id) {
const employeeMap = new Map();
for (const e of employees) {
employeeMap.set(e.id, e);
}
const queue = [id];
let totalImportance = 0;
while (queue.length > 0) {
const currentId = queue.shift();
const employee = employeeMap.get(currentId);
totalImportance += employee.importance;
for (const subId of employee.subordinates) {
queue.push(subId);
}
}
return totalImportance;
}using System.Collections.Generic;
class Employee {
public int id;
public int importance;
public IList<int> subordinates;
}
class Solution {
public int GetImportance(IList<Employee> employees, int id) {
var employeeMap = new Dictionary<int, Employee>();
foreach (var e in employees) {
employeeMap[e.id] = e;
}
var queue = new Queue<int>();
queue.Enqueue(id);
int totalImportance = 0;
while (queue.Count > 0) {
int currentId = queue.Dequeue();
var employee = employeeMap[currentId];
totalImportance += employee.importance;
foreach (var subId in employee.subordinates) {
queue.Enqueue(subId);
}
}
return totalImportance;
}
}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.
Time Complexity: O(N), as it processes each employee once.
Space Complexity: O(N), due to the queue and employee mapping storage.
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.
/**
* Definition for Employee.
* class Employee {
* id: number
* importance: number
* subordinates: number[]
* constructor(id: number, importance: number, subordinates: number[]) {
* this.id = (id === undefined) ? 0 : id;
* this.importance = (importance === undefined) ? 0 : importance;
* this.subordinates = (subordinates === undefined) ? [] : subordinates;
* }
* }
*/
function getImportance(employees: Employee[], id: number): number {
const d = new Map<number, Employee>();
for (const e of employees) {
d.set(e.id, e);
}
const dfs = (i: number): number => {
let s = d.get(i)!.importance;
for (const j of d.get(i)!.subordinates) {
s += dfs(j);
}
return s;
};
return dfs(id);
}/**
* Definition for Employee.
* type Employee struct {
* Id int
* Importance int
* Subordinates []int
* }
*/
func getImportance(employees []*Employee, id int) int {
d := map[int]*Employee{}
for _, e := range employees {
d[e.Id] = e
}
var dfs func(int) int
dfs = func(i int) int {
s := d[i].Importance
for _, j := range d[i].Subordinates {
s += dfs(j)
}
return s
}
return dfs(id)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Depth-First Search (DFS) using Recursion | Time Complexity: O(N), where N is the number of employees, as each employee is visited once. |
| Breadth-First Search (BFS) using Queue | Time Complexity: O(N), as it processes each employee once. |
| Hash Table + DFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS using Recursion + Hash Map | O(n) | O(n) | Most common interview solution. Clean recursive traversal of the hierarchy. |
| BFS using Queue + Hash Map | O(n) | O(n) | Preferred when avoiding recursion or when iterative traversal is required. |
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.