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.

Examples

Example 1:

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:

Input: employees = [[1,2,[5]],[5,-3,[]]], id = 5
Output: -3
Explanation: Employee 5 has an importance value of -3 and has no 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.

Thinking Process

  1. Hash map for lookup: Essential for O(1) employee access
  • BFS visits nodes in non-decreasing distance from the source.
  • Queue guarantees shortest path in unweighted graphs.
  • Process level by level when counting layers or distances.
Graph BFS layers S a b t BFS: expand by layers (queue)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Recursive DFS (this problem) O(n) O(h) stack Natural for trees and graphs
Iterative DFS (stack) O(n) O(n) Avoid recursion depth limits
DFS with memoization O(n) O(n) Overlapping subproblems on graphs
Backtracking DFS O(2^n) typical O(n) Enumerate choices with pruning

Solution

Time Complexity: O(n) - Visit each employee once
Space Complexity: O(n) - Hash map + recursion stack

/*
// Definition for Employee.
class Employee {
public:
    int id;
    int importance;
    vector<int> subordinates;
};
*/

class Solution {
private:
    unordered_map<int, Employee*> emap;
    
    int dfs(int id) {
        Employee* employee = emap[id];
        int rtn = employee->importance;
        for(int subid: employee->subordinates) {
            rtn += dfs(subid);
        }
        return rtn;
    }
    
public:
    int getImportance(vector<Employee*> employees, int id) {
        emap.clear();
        for(auto& e: employees) {
            emap[e->id] = e;
        }
        return dfs(id);
    }
};

Solution Explanation

Approach: Recursive DFS (this problem)

Key idea: 1. Hash map for lookup: Essential for O(1) employee access

How the code works:

  1. Hash map for lookup: Essential for O(1) employee access
    • BFS visits nodes in non-decreasing distance from the source.
    • Queue guarantees shortest path in unweighted graphs.
    • Process level by level when counting layers or distances.

Walkthrough — input employees = [[1,5,[2,3]],[2,3,[]],[3,3,[]]], id = 1, expected 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.

Operation Time Space
Build hash map O(n) O(n)
DFS/BFS traversal O(n) O(n)
Overall O(n) O(n)

How Solution 1 Works

  1. Build hash map: Map employee ID to Employee pointer for O(1) lookup
  2. DFS traversal:
    • Start from the given employee
    • Add their importance value
    • Recursively add importance of all subordinates
  3. Return total: Sum of employee’s importance + all subordinates’ importance

    Example Walkthrough

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

Employee Structure:
    1 (importance: 5)
   / \
  2   3
(3)  (3)

DFS Traversal:
1. Start at employee 1: importance = 5
2. Visit subordinate 2: importance = 3
3. Visit subordinate 3: importance = 3
4. Total = 5 + 3 + 3 = 11

Complexity

| Operation | Time | Space | |———–|——|——-| | Build hash map | O(n) | O(n) | | DFS/BFS traversal | O(n) | O(n) | | Overall | O(n) | O(n) |

Common Mistakes

  1. Single employee: No subordinates, return their importance
  2. Negative importance: Handle negative values correctly
  3. Deep hierarchy: Recursion handles deep trees

  4. Wide hierarchy: Many direct subordinates

  5. Linear search: Not using hash map for O(1) lookup
  6. Missing subordinates: Not traversing all levels
  7. Wrong starting point: Starting from wrong employee ID

Pattern Recognition

This problem demonstrates the “Tree/Graph Traversal with Hash Map” pattern:

1. Build hash map for O(1) node lookup
2. Use DFS or BFS to traverse
3. Accumulate values during traversal

References

Key Takeaways

  1. Hash map for lookup: Essential for O(1) employee access
  2. Tree traversal: Employee hierarchy is a tree structure
  3. DFS vs BFS: Both work equally well for this problem