# Employee Importance
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/employee-importance)
Canonical: https://scaleengineer.com/dsa/problems/employee-importance
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Hash Table, Tree
**Companies:** [Rippling](https://scaleengineer.com/companies/rippling), [Robinhood](https://scaleengineer.com/companies/robinhood)
---
## 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].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:**

![](https://assets.glich.co/dsa/employee-importance/image0.jpg) 

**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:**

![](https://assets.glich.co/dsa/employee-importance/image1.jpg) 

**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.

# Approaches
## Brute-Force Search
This approach directly traverses the employee hierarchy starting from the given ID. For each employee encountered during the traversal, it performs a linear search through the entire input list to find their details. This method avoids any preprocessing but results in a significant performance penalty due to the repeated searches.
**Time:** O(N*K), where N is the total number of employees and K is the number of employees in the hierarchy of the given `id`. The traversal visits K employees, and for each one, it scans the list of N employees. In the worst case, K=N, leading to O(N^2). · **Space:** O(N), where N is the total number of employees. In the worst case, the queue could hold up to N-1 subordinates.
**Pros:** Simple to conceptualize without complex data structures.; Uses minimal extra space besides the queue for traversal.
**Cons:** Extremely inefficient for larger inputs, with a time complexity of O(N^2) in the worst case.; Performs a lot of redundant work by repeatedly scanning the entire list of employees.
### Explanation
In this brute-force method, we use a queue to perform a Breadth-First Search (BFS) starting with the initial employee ID. We initialize a running total for the importance value. In a loop, we process one employee ID from the queue at a time. The core inefficiency lies in how we retrieve employee details: for each ID, we must iterate through the entire `employees` list to find the matching `Employee` object. Once the employee is found, we add their importance to our total and add all their subordinate IDs to the queue for future processing. This continues until the queue is empty, meaning we have visited the initial employee and all their direct and indirect subordinates.

```java
/*
// Definition for Employee.
class Employee {
    public int id;
    public int importance;
    public List<Integer> subordinates;
};
*/
class Solution {
    public int getImportance(List<Employee> employees, int id) {
        int totalImportance = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(id);

        while (!queue.isEmpty()) {
            int currentId = queue.poll();
            // Inefficiently find the employee by iterating through the list
            for (Employee emp : employees) {
                if (emp.id == currentId) {
                    totalImportance += emp.importance;
                    for (int subordinateId : emp.subordinates) {
                        queue.offer(subordinateId);
                    }
                    break; // Found the employee, can break inner loop
                }
            }
        }
        return totalImportance;
    }
}
```
### Algorithm
1. Initialize `totalImportance` to 0.
2. Create a queue (e.g., `LinkedList`) and add the starting `id` to it.
3. Loop while the queue is not empty:
    a. Dequeue an `employeeId`.
    b. Iterate through the entire `employees` list to find the `Employee` object whose `id` matches `employeeId`.
    c. Once found, add the employee's `importance` to `totalImportance`.
    d. Add all of the employee's `subordinates` to the queue.
    e. Break the inner loop and continue to the next ID in the queue.
4. After the loop finishes, return `totalImportance`.

## Breadth-First Search (BFS) with a HashMap
This approach significantly optimizes the traversal by first preprocessing the employee list into a HashMap. This map allows for constant-time O(1) lookups of any employee by their ID. After this one-time setup, a standard Breadth-First Search (BFS) is performed to traverse the hierarchy and sum the importance values efficiently.
**Time:** O(N), where N is the total number of employees. It takes O(N) to build the map and O(K) for the BFS traversal (where K is the number of employees in the subtree, K <= N). The total time complexity is dominated by O(N). · **Space:** O(N), where N is the total number of employees. This space is used for the HashMap and the queue. The queue's maximum size can be O(N) in the case of a very wide hierarchy.
**Pros:** Highly efficient with a linear time complexity of O(N).; The iterative nature of BFS avoids the risk of stack overflow errors that can occur with deep recursion.
**Cons:** Requires extra space of O(N) to store the HashMap.
### Explanation
The key to this efficient approach is the preprocessing step. We create a `HashMap` where keys are employee IDs and values are the `Employee` objects themselves. We iterate through the input `employees` list just once to populate this map. This step takes O(N) time, where N is the number of employees.

With the map ready, we can find any employee's data in O(1) time. We then use a `Queue` to perform a BFS traversal, starting with the initial `id`. We initialize `totalImportance` to 0. While the queue is not empty, we dequeue an employee ID, use our map to instantly retrieve their `Employee` object, add their importance to the total, and enqueue all their subordinate IDs. This process ensures that every employee in the specified hierarchy is visited exactly once, leading to a linear time complexity.

```java
/*
// Definition for Employee.
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> empMap = new HashMap<>();
        for (Employee emp : employees) {
            empMap.put(emp.id, emp);
        }

        int totalImportance = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(id);

        while (!queue.isEmpty()) {
            int currentId = queue.poll();
            Employee currentEmp = empMap.get(currentId);
            totalImportance += currentEmp.importance;
            for (int subordinateId : currentEmp.subordinates) {
                queue.offer(subordinateId);
            }
        }
        return totalImportance;
    }
}
```
### Algorithm
1. Create a `HashMap<Integer, Employee>` to map employee IDs to `Employee` objects.
2. Iterate through the input `employees` list once to populate the map. This provides O(1) lookup time for any employee.
3. Initialize `totalImportance = 0`.
4. Create a `Queue<Integer>` and add the initial `id`.
5. While the queue is not empty:
    a. Dequeue an `employeeId`.
    b. Get the corresponding `Employee` object from the HashMap in O(1) time.
    c. Add the employee's `importance` to `totalImportance`.
    d. For each `subordinateId` in the employee's `subordinates` list, enqueue it.
6. Return `totalImportance`.

## Depth-First Search (DFS) with a HashMap
This approach also uses a HashMap for efficient O(1) employee lookups, but it employs a Depth-First Search (DFS) traversal instead of BFS. DFS explores as far as possible down one branch before backtracking. This is naturally implemented using recursion, which can lead to very clean and concise code.
**Time:** O(N), where N is the total number of employees. O(N) for building the map and O(K) for the DFS traversal (where K is the number of employees in the subtree, K <= N). The total time complexity is O(N). · **Space:** O(N). O(N) is used for the HashMap. The recursion call stack also uses space, which is proportional to the depth of the hierarchy, H. In the worst-case scenario of a skewed tree, H can be N, leading to O(N) space complexity.
**Pros:** Efficient with O(N) time complexity.; The recursive solution is often very elegant, concise, and easy to understand.
**Cons:** Requires O(N) extra space for the HashMap.; The recursive implementation can lead to a `StackOverflowError` if the employee hierarchy is very deep (i.e., a tall and skinny tree structure).
### Explanation
Similar to the BFS approach, the first step is to build a `HashMap` that maps employee IDs to `Employee` objects. This O(N) preprocessing step is crucial for efficiency.

Once the map is built, we use a recursive helper function to perform the DFS. The function, say `dfs(employeeId)`, calculates the total importance for the subtree rooted at `employeeId`. It does this by first getting the importance of the `employeeId` itself. Then, it iterates through all direct subordinates and makes a recursive call for each one. The sum of the results from these recursive calls is added to the current employee's importance. The base case for the recursion is an employee with no subordinates, where the function simply returns that employee's own importance.

```java
/*
// Definition for Employee.
class Employee {
    public int id;
    public int importance;
    public List<Integer> subordinates;
};
*/
class Solution {
    Map<Integer, Employee> empMap;

    public int getImportance(List<Employee> employees, int id) {
        empMap = new HashMap<>();
        for (Employee emp : employees) {
            empMap.put(emp.id, emp);
        }
        return dfs(id);
    }

    private int dfs(int employeeId) {
        Employee employee = empMap.get(employeeId);
        int totalImportance = employee.importance;
        for (int subordinateId : employee.subordinates) {
            totalImportance += dfs(subordinateId);
        }
        return totalImportance;
    }
}
```
### Algorithm
1. Create a `HashMap<Integer, Employee>` and populate it from the `employees` list for O(1) lookups.
2. Define a recursive helper function, let's call it `dfs(employeeId)`.
3. The main function calls `dfs(id)` with the starting employee ID and returns the result.
4. The `dfs(employeeId)` function works as follows:
    a. Look up the `Employee` object for the current `employeeId` in the HashMap.
    b. Initialize a local variable `importanceSum` with the current employee's `importance`.
    c. Iterate through the `subordinates` list of the current employee.
    d. For each `subordinateId`, make a recursive call `dfs(subordinateId)` and add the returned value to `importanceSum`.
    e. Return `importanceSum`.

# Solutions
### Java

```java
/* // Definition for Employee. class Employee { public int id; public int importance; public List<Integer> subordinates; }; */ class Solution { private final Map < Integer , Employee > map = new HashMap <>(); public int getImportance ( List < Employee > employees , int id ) { for ( Employee employee : employees ) { map . put ( employee . id , employee ); } return dfs ( id ); } private int dfs ( int id ) { Employee employee = map . get ( id ); int sum = employee . importance ; for ( Integer subordinate : employee . subordinates ) { sum += dfs ( subordinate ); } return sum ; } }
```

### JavaScript

```javascript
/** * Definition for Employee. * function Employee(id, importance, subordinates) { * this.id = id; * this.importance = importance; * this.subordinates = subordinates; * } */ /** * @param {Employee[]} employees * @param {number} id * @return {number} */ var GetImportance =
  function (employees, id) {
    const map = new Map();
    for (const employee of employees) {
      map.set(employee.id, employee);
    }
    const dfs = (id) => {
      const employee = map.get(id);
      let sum = employee.importance;
      for (const subId of employee.subordinates) {
        sum += dfs(subId);
      }
      return sum;
    };
    return dfs(id);
  };

```

### CPP

```cpp
/* // Definition for Employee. class Employee { public: int id; int importance; vector<int> subordinates; }; */ class Solution { public: int getImportance ( vector < Employee *> employees , int id ) { unordered_map < int , Employee *> d ; for ( auto & e : employees ) { d [ e -> id ] = e ; } function < int ( int ) > dfs = [ & ]( int i ) -> int { int s = d [ i ] -> importance ; for ( int j : d [ i ] -> subordinates ) { s += dfs ( j ); } return s ; }; return dfs ( id ); } };
```

### Python

```python
""" # Definition for Employee. class Employee: def __init__(self, id: int, importance: int, subordinates: List[int]): self.id = id self.importance = importance self.subordinates = subordinates """ class Solution : def getImportance ( self , employees : List [ 'Employee' ], id : int ) -> int : m = { emp . id : emp for emp in employees } def dfs ( id : int ) -> int : emp = m [ id ] s = emp . importance for sub in emp . subordinates : s += dfs ( sub ) return s return dfs ( id )
```