# LeetCode 690: Employee Importance

## Problem Restatement

We are given a list of employees.

Each employee has:

| Field | Meaning |
|---|---|
| `id` | Unique employee ID |
| `importance` | Integer importance value |
| `subordinates` | List of direct subordinate IDs |

Given an employee ID, return the total importance of that employee and all their direct and indirect subordinates. The official statement asks for the sum of the importance values for the given employee, plus every employee under them in the hierarchy.

Direct subordinates are listed immediately under the employee.

Indirect subordinates are subordinates of subordinates, and so on.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `employees`, a list of `Employee` objects, and an integer `id` |
| Output | Total importance value |
| Lookup key | Employee ID |
| Traversal | Start from the given employee and visit all subordinates |

Example function shape:

```python
def getImportance(employees: list["Employee"], id: int) -> int:
    ...
```

The LeetCode class shape is:

```python
class Employee:
    def __init__(self, id: int, importance: int, subordinates: list[int]):
        self.id = id
        self.importance = importance
        self.subordinates = subordinates
```

## Examples

Example 1:

```python
employees = [
    [1, 5, [2, 3]],
    [2, 3, []],
    [3, 3, []],
]
id = 1
```

Employee `1` has importance `5`.

Employee `1` has two direct subordinates:

| Employee | Importance |
|---:|---:|
| `2` | `3` |
| `3` | `3` |

Total:

```text
5 + 3 + 3 = 11
```

Answer:

```python
11
```

Example 2:

```python
employees = [
    [1, 2, [5]],
    [5, -3, []],
]
id = 5
```

We start from employee `5`.

Employee `5` has importance `-3` and no subordinates.

Answer:

```python
-3
```

## First Thought: Search the List Every Time

A direct solution is to recursively process the employee and their subordinates.

But if we only have a list, then each time we need an employee by ID, we may scan the whole list.

For example, to find employee `17`, we might do:

```python
for employee in employees:
    if employee.id == 17:
        return employee
```

If we do this for many subordinates, the repeated lookup becomes expensive.

We need fast access by employee ID.

## Key Insight

Employee IDs are unique.

So we can build a hash map:

```python
id_to_employee[id] = employee
```

Then every employee lookup becomes expected `O(1)`.

After that, the problem is just a traversal of a tree-like hierarchy:

1. Visit the current employee.
2. Add their importance.
3. Visit every subordinate.
4. Add each subordinate's total importance.

This can be done with DFS or BFS.

## Algorithm

1. Build a dictionary from employee ID to employee object.
2. Define a DFS function `dfs(employee_id)`.
3. In `dfs`:
   - Get the employee object from the dictionary.
   - Start `total` with the employee's own importance.
   - For each subordinate ID:
     - Add `dfs(subordinate_id)` to `total`.
   - Return `total`.
4. Return `dfs(id)`.

## Walkthrough

Consider:

```python
employees = [
    Employee(1, 5, [2, 3]),
    Employee(2, 3, []),
    Employee(3, 3, []),
]
id = 1
```

Build the map:

| ID | Importance | Subordinates |
|---:|---:|---|
| `1` | `5` | `[2, 3]` |
| `2` | `3` | `[]` |
| `3` | `3` | `[]` |

Start DFS at employee `1`.

```text
dfs(1)
```

Employee `1` contributes `5`.

Then visit subordinate `2`:

```text
dfs(2) = 3
```

Then visit subordinate `3`:

```text
dfs(3) = 3
```

So:

```text
dfs(1) = 5 + 3 + 3 = 11
```

Return:

```python
11
```

## Correctness

The dictionary maps each employee ID to exactly the corresponding employee object, because employee IDs are unique.

The DFS starts from the requested employee ID.

For each visited employee, the algorithm adds that employee's own importance exactly once.

Then it recursively visits every direct subordinate listed for that employee.

By recursion, each subordinate call returns the total importance of that subordinate and all employees below them.

Therefore, the current call returns the employee's own importance plus the total importance of every direct and indirect subordinate.

This is exactly the value requested by the problem.

Because the DFS starts at the given ID, it visits precisely the employee's hierarchy and returns the correct total importance.

## Complexity

Let `n` be the number of employees under consideration.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Build the map once and visit each reachable employee once |
| Space | `O(n)` | Store the ID map and recursion stack in the worst case |

If the hierarchy depth is `h`, the recursion stack is `O(h)`.

The hash map itself is `O(n)`.

## Implementation

```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:
        id_to_employee = {}

        for employee in employees:
            id_to_employee[employee.id] = employee

        def dfs(employee_id: int) -> int:
            employee = id_to_employee[employee_id]

            total = employee.importance

            for subordinate_id in employee.subordinates:
                total += dfs(subordinate_id)

            return total

        return dfs(id)
```

## Code Explanation

We first build the lookup table:

```python
id_to_employee = {}

for employee in employees:
    id_to_employee[employee.id] = employee
```

This lets us get any employee by ID in constant expected time.

The recursive function:

```python
def dfs(employee_id: int) -> int:
```

returns the total importance of that employee and everyone below them.

We fetch the employee:

```python
employee = id_to_employee[employee_id]
```

Start with their own importance:

```python
total = employee.importance
```

Then add each subordinate's total:

```python
for subordinate_id in employee.subordinates:
    total += dfs(subordinate_id)
```

Finally, return the accumulated value:

```python
return total
```

The public method returns the DFS result for the requested employee:

```python
return dfs(id)
```

## Iterative BFS Version

DFS is concise, but BFS also works.

```python
from collections import deque

class Solution:
    def getImportance(self, employees: list["Employee"], id: int) -> int:
        id_to_employee = {employee.id: employee for employee in employees}

        queue = deque([id])
        total = 0

        while queue:
            employee_id = queue.popleft()
            employee = id_to_employee[employee_id]

            total += employee.importance

            for subordinate_id in employee.subordinates:
                queue.append(subordinate_id)

        return total
```

This version avoids recursion depth concerns.

## Testing

```python
class Employee:
    def __init__(self, id: int, importance: int, subordinates: list[int]):
        self.id = id
        self.importance = importance
        self.subordinates = subordinates

def run_tests():
    s = Solution()

    employees = [
        Employee(1, 5, [2, 3]),
        Employee(2, 3, []),
        Employee(3, 3, []),
    ]
    assert s.getImportance(employees, 1) == 11

    employees = [
        Employee(1, 2, [5]),
        Employee(5, -3, []),
    ]
    assert s.getImportance(employees, 5) == -3

    employees = [
        Employee(1, 10, [2]),
        Employee(2, 5, [3]),
        Employee(3, 1, []),
    ]
    assert s.getImportance(employees, 1) == 16

    employees = [
        Employee(1, 10, [2, 3]),
        Employee(2, -5, []),
        Employee(3, 7, []),
    ]
    assert s.getImportance(employees, 1) == 12

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Expected | Why |
|---|---:|---|
| Employee `1` with subordinates `2` and `3` | `11` | Official example |
| Start from employee `5` | `-3` | Employee has no subordinates |
| Chain `1 -> 2 -> 3` | `16` | Checks indirect subordinates |
| Negative importance | `12` | Importance values can reduce the total |