LeetCode 690: Employee Importance

Problem Restatement

We are given a list of employees.

Each employee has:

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

Example function shape:

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

The LeetCode class shape is:

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

Examples

Example 1:

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

Employee 1 has importance 5.

Employee 1 has two direct subordinates:

Total:

5 + 3 + 3 = 11

Answer:

11

Example 2:

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

We start from employee 5.

Employee 5 has importance -3 and no subordinates.

Answer:

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

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:

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:

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

Build the map:

Start DFS at employee 1.

dfs(1)

Employee 1 contributes 5.

Then visit subordinate 2:

dfs(2) = 3

Then visit subordinate 3:

dfs(3) = 3

So:

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

Return:

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.

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

The hash map itself is O(n).

Implementation

"""
# 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:

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:

def dfs(employee_id: int) -> int:

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

We fetch the employee:

employee = id_to_employee[employee_id]

Start with their own importance:

total = employee.importance

Then add each subordinate’s total:

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

Finally, return the accumulated value:

return total

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

return dfs(id)

Iterative BFS Version

DFS is concise, but BFS also works.

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

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: