#690

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Employee Importance

Calculate an employee's total importance including all direct and indirect subordinates using array scanning and hash lookup efficiently.

array hash table tree depth first search breadth first search

Problem Statement

You are given a list of employees where each employee is represented as [id, importance, subordinates], with a unique integer ID, an importance value, and a list of direct subordinate IDs. Your task is to compute the total importance value of a given employee, including all levels of subordinates, not just the direct reports.

Given an integer id representing the employee to evaluate, return the sum of their importance and the importance of all their direct and indirect subordinates. Efficiently accessing employees by ID using a hash table is key to avoid repeated array scans while handling nested subordinate relationships.

Examples

Example 1

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

Output: 11

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

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.

Solution Approach

Build an ID-to-Employee Map

Create a hash table mapping each employee's ID to their data structure. This allows constant-time lookup for any subordinate ID, avoiding repeated O(N) array scans when traversing subordinates.

Recursive Depth-First Sum

Implement a DFS function that, given an employee ID, returns the employee's importance plus the sum of all subordinates' importance recursively. This handles deep hierarchy structures while leveraging the hash map for O(1) lookups.

Iterative Breadth-First Alternative

Use a queue for BFS traversal starting with the target employee ID. Dequeue each employee, add their importance to a running total, and enqueue all direct subordinates. This avoids stack overflow in very deep trees and still benefits from hash table lookup.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(N)

Time complexity is O(N) because each employee is visited once through either DFS or BFS. Space complexity is O(N) due to the hash map and potential recursion stack or BFS queue storage.

What Interviewers Usually Probe

Look for candidates building a hash map to avoid repeated array scans.
Watch if recursion correctly handles indirect subordinates in nested hierarchies.
Check for both DFS and BFS awareness in accumulating total importance.

Common Pitfalls or Variants

Common pitfalls

Summing only direct subordinates and ignoring deeper levels.
Repeatedly scanning the employee array instead of using a hash map for O(1) lookups.
Failing to handle employees with negative importance values correctly.

Follow-up variants

Compute total importance but return the highest importance path in the hierarchy instead of the sum.
Allow dynamic addition or removal of subordinates and recalculate importance on the fly.
Calculate importance with constraints on maximum traversal depth for partial aggregation scenarios.

FAQ

What is the best way to compute total importance for Employee Importance problem?

Use a hash map to map employee IDs for O(1) access, then traverse subordinates recursively or with BFS to sum all importance values.

Can BFS be used instead of DFS for this problem?

Yes, BFS with a queue accumulates importance while preventing deep recursion issues and still uses the hash map for efficient lookups.

How do negative importance values affect the solution?

Negative values are valid and should be added normally; they do not change the traversal logic but affect the total sum.

What if an employee has no subordinates?

Simply return their own importance value, as there are no subordinates to include in the sum.

Why is hash table lookup essential in this array scanning plus hash lookup pattern?

Without a hash table, each subordinate lookup would require O(N) scans, making the solution inefficient for large employee arrays.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

"""
# 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:
        def dfs(i: int) -> int:
            return d[i].importance + sum(dfs(j) for j in d[i].subordinates)

        d = {e.id: e for e in employees}
        return dfs(id)

Continue Practicing

#721 accounts merge #653 two sum iv input is a bst #839 similar string groups