LeetCode 690 - Employee Importance

LeetCode Problem 690

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Tree, Depth-First Search, Breadth-First Search

Solution

Problem Understanding

The problem provides a collection of employees where each employee contains three pieces of information:

• A unique employee ID
• An integer importance value
• A list of IDs representing their direct subordinates

We are also given the ID of one employee, and we must calculate the total importance for that employee and everyone under them in the organizational hierarchy, including both direct and indirect subordinates.

In other words, this is a traversal problem over a management tree. Starting from a specific employee, we need to visit every employee reachable through subordinate relationships and sum all their importance values.

The input is not given as an explicit tree structure with pointers between nodes. Instead, employees are stored in a flat array. Each employee references subordinates only by ID. This means that before traversing the hierarchy efficiently, we need a way to quickly map an ID to its corresponding employee object.

The constraints tell us several important things:

• There can be up to 2000 employees, which is large enough that repeated linear scans become inefficient.
• Employee IDs are unique, which makes them ideal keys for a hash map.
• Each employee can have at most one manager, so the structure forms a valid tree or forest without cycles.
• Subordinate IDs are guaranteed to be valid, so we do not need defensive checks for missing employees.

The key challenge is efficiently navigating from one employee ID to its employee object while recursively or iteratively exploring all descendants.

Several edge cases are important:

• The requested employee may have no subordinates.
• Importance values may be negative.
• The hierarchy may be very deep.
• The hierarchy may branch widely with many subordinates.
• The starting employee could be anywhere in the organization, not necessarily the root.

Because the input guarantees a valid hierarchy with unique IDs and no cycles, we can safely perform DFS or BFS traversal without worrying about infinite loops.

Approaches

Brute Force Approach

A straightforward solution is to recursively search for employees by scanning the entire employee list every time we encounter a subordinate ID.

The idea works like this:

1. Start with the given employee ID.
2. Scan the entire employees array to find the matching employee.
3. Add that employee's importance.
4. Recursively repeat the process for each subordinate.

This approach is correct because it eventually visits every subordinate exactly once and accumulates all importance values.

However, it is inefficient because every employee lookup requires a full scan of the employee list. If there are n employees and we potentially perform a lookup for each employee, the total time complexity becomes quadratic.

With up to 2000 employees, this still might pass in practice, but it is unnecessarily slow and does not scale well.

Optimal Approach

The key insight is that employee IDs are unique, so we can preprocess the employee list into a hash map.

The hash map allows us to retrieve an employee object in constant time using its ID.

After building this lookup table, the problem becomes a standard graph or tree traversal problem. We can use either:

• Depth-First Search (DFS)
• Breadth-First Search (BFS)

DFS is especially natural here because the hierarchy is recursive by definition. For each employee:

• Add their importance
• Recursively process all subordinates

Each employee is visited exactly once, and each lookup is O(1).

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(h)	Repeatedly scans employee list for every lookup
Optimal	O(n)	O(n)	Uses hash map for constant-time employee lookup

Here, h represents the recursion depth of the hierarchy.

Algorithm Walkthrough

1. Create a hash map called employee_map where the key is the employee ID and the value is the employee object itself.

This preprocessing step is critical because the input is given as a flat list rather than a connected structure. Without the map, we would need repeated linear searches. 2. Define a DFS helper function that accepts an employee ID.

The helper function will:

• Retrieve the employee from the hash map
• Start with that employee's importance value
• Recursively visit each subordinate
• Add subordinate importance totals to the running sum

3. Inside the DFS function, initialize a variable called total_importance with the current employee's importance.

This ensures the employee's own contribution is included before processing subordinates. 4. Iterate through the current employee's subordinates list.

For each subordinate ID:

• Recursively call DFS
• Add the returned value to total_importance

5. Return the accumulated total from the DFS function.

By the time recursion finishes, the total contains the importance of the current employee and every descendant in the hierarchy. 6. Start the traversal by calling DFS on the given id. 7. Return the final result.

Why it works

The algorithm works because the organizational hierarchy forms a tree-like structure with no cycles. DFS guarantees that every reachable subordinate is visited exactly once.

At each recursive call, the function correctly computes:

• The employee's own importance
• Plus the total importance of all subordinate subtrees

Because recursive results are combined additively, the final answer is the complete importance total for the entire hierarchy rooted at the given employee.

Python Solution

from typing import List

"""
# 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:
        employee_map = {employee.id: employee for employee in employees}

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

            total_importance = employee.importance

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

            return total_importance

        return dfs(id)

The implementation begins by constructing a dictionary called employee_map. This converts the flat employee list into an efficient lookup structure where any employee can be accessed in constant time using their ID.

The nested dfs function performs the recursive traversal. It first retrieves the employee object associated with the provided ID. The employee's own importance is added immediately because every employee contributes to the total.

The function then iterates through all subordinate IDs and recursively computes each subordinate's total importance. Those results are accumulated into total_importance.

Finally, the outer method simply starts the DFS traversal from the requested employee ID and returns the computed total.

This implementation is concise because the recursive structure naturally mirrors the hierarchy itself.

Go Solution

/**
 * Definition for Employee.
 * type Employee struct {
 *     Id int
 *     Importance int
 *     Subordinates []int
 * }
 */

func getImportance(employees []*Employee, id int) int {
    employeeMap := make(map[int]*Employee)

    for _, employee := range employees {
        employeeMap[employee.Id] = employee
    }

    var dfs func(int) int

    dfs = func(employeeID int) int {
        employee := employeeMap[employeeID]

        totalImportance := employee.Importance

        for _, subordinateID := range employee.Subordinates {
            totalImportance += dfs(subordinateID)
        }

        return totalImportance
    }

    return dfs(id)
}

The Go implementation follows the same overall structure as the Python version. A map is used for constant-time employee lookup, and a recursive DFS function computes the total importance.

One Go-specific detail is that employees are stored as pointers (*Employee) in the map, which avoids unnecessary copying of structs.

The recursive DFS function is declared using a variable assignment because recursive anonymous functions in Go require the variable to exist before assignment.

Go slices naturally handle empty subordinate lists, so no special nil checks are required.

Worked Examples

Example 1

Input:

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

Step 1: Build the hash map

Employee ID	Importance	Subordinates
1	5	[2, 3]
2	3	[]
3	3	[]

Step 2: Start DFS at employee 1

Current employee:

Variable	Value
employee_id	1
total_importance	5

Subordinates are [2, 3].

Step 3: Visit subordinate 2

Variable	Value
employee_id	2
total_importance	3

Employee 2 has no subordinates.

Return value:

3

Back at employee 1:

total_importance = 5 + 3 = 8

Step 4: Visit subordinate 3

Variable	Value
employee_id	3
total_importance	3

Employee 3 has no subordinates.

Return value:

3

Back at employee 1:

total_importance = 8 + 3 = 11

Final Answer

11

Example 2

Input:

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

Step 1: Build the hash map

Employee ID	Importance	Subordinates
1	2	[5]
5	-3	[]

Step 2: Start DFS at employee 5

Variable	Value
employee_id	5
total_importance	-3

Employee 5 has no subordinates.

Return value:

-3

Final Answer

-3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each employee is processed exactly once
Space	O(n)	Hash map storage plus recursion stack

The hash map construction requires O(n) time because every employee is inserted once.

The DFS traversal also visits each employee exactly once. Since each subordinate relationship is traversed once, the total traversal cost remains linear.

The space complexity comes primarily from the hash map storing all employees. The recursion stack may also grow up to the height of the hierarchy in the worst case.

Test Cases

from typing import List

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:
        employee_map = {employee.id: employee for employee in employees}

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

            total_importance = employee.importance

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

            return total_importance

        return dfs(id)

solution = Solution()

# Example 1
employees1 = [
    Employee(1, 5, [2, 3]),
    Employee(2, 3, []),
    Employee(3, 3, [])
]
assert solution.getImportance(employees1, 1) == 11  # basic hierarchy

# Example 2
employees2 = [
    Employee(1, 2, [5]),
    Employee(5, -3, [])
]
assert solution.getImportance(employees2, 5) == -3  # negative importance

# Single employee
employees3 = [
    Employee(1, 10, [])
]
assert solution.getImportance(employees3, 1) == 10  # no subordinates

# Deep hierarchy
employees4 = [
    Employee(1, 1, [2]),
    Employee(2, 2, [3]),
    Employee(3, 3, [4]),
    Employee(4, 4, [])
]
assert solution.getImportance(employees4, 1) == 10  # chain structure

# Wide hierarchy
employees5 = [
    Employee(1, 10, [2, 3, 4, 5]),
    Employee(2, 1, []),
    Employee(3, 1, []),
    Employee(4, 1, []),
    Employee(5, 1, [])
]
assert solution.getImportance(employees5, 1) == 14  # many direct subordinates

# Start from non-root employee
employees6 = [
    Employee(1, 5, [2]),
    Employee(2, 3, [3]),
    Employee(3, 2, [])
]
assert solution.getImportance(employees6, 2) == 5  # subtree only

# Zero total importance
employees7 = [
    Employee(1, 5, [2]),
    Employee(2, -5, [])
]
assert solution.getImportance(employees7, 1) == 0  # positive and negative cancel

Test	Why
Basic hierarchy	Verifies normal recursive traversal
Negative importance	Ensures negative values are handled correctly
Single employee	Tests smallest valid input
Deep hierarchy	Tests recursive depth behavior
Wide hierarchy	Tests multiple direct subordinates
Non-root starting node	Ensures traversal works from any employee
Zero total importance	Verifies correct arithmetic accumulation

Edge Cases

One important edge case occurs when the starting employee has no subordinates. In this scenario, the algorithm should simply return the employee's own importance value without performing additional recursion. A buggy implementation might incorrectly assume every employee has subordinates or mishandle empty lists. This implementation handles the case naturally because iterating over an empty subordinate list performs zero recursive calls.

Another important case is negative importance values. Since the problem allows importance values between -100 and 100, the total importance can decrease as subordinates are processed. Some implementations incorrectly assume all importance values are positive and may initialize totals improperly. This solution always adds values exactly as given, so negative contributions are handled correctly.

A third critical edge case is a very deep hierarchy where each employee has exactly one subordinate. This creates a linked-list-like structure. Recursive solutions must correctly propagate accumulated totals back through all recursive calls. Because the DFS function returns the full subtotal for every subtree, the accumulation remains correct regardless of hierarchy depth.

A fourth subtle edge case is starting from a non-root employee. The problem does not guarantee that the requested employee is the top-level manager. The algorithm correctly computes only the subtree rooted at the requested employee because traversal begins specifically from the provided ID rather than assuming traversal should start at the organizational root.