Problem Description

The Employee Importance problem asks you to calculate the total importance value of an employee and all their direct and indirect subordinates. You are given:

• A list of Employee objects, where each object contains:
  • id: Unique integer ID of the employee.
  • importance: Integer value representing the employee's importance.
  • subordinates: List of IDs of the employee's direct subordinates.
• An integer id representing the employee whose total importance you need to find.

Your task is to return the sum of the importance values for the given employee and all their subordinates (both direct and indirect).

Constraints:

• Each employee has a unique id.
• There is exactly one employee with the given id.
• Employees may have zero or more subordinates.
• All subordinates are also listed as employees in the input.

Thought Process

To solve this problem, we need to efficiently compute the total importance for a given employee, including all their direct and indirect subordinates. At first glance, one might consider iterating through the list of employees for each subordinate, summing up their importance recursively. However, this would be inefficient due to repeated searches for employee objects by id.

To optimize, it makes sense to map each id to its corresponding Employee object for fast lookup. This allows us to traverse the hierarchy using either Depth-First Search (DFS) or Breadth-First Search (BFS), visiting each employee exactly once. This approach eliminates redundant searches and ensures that we only process each employee a single time.

Solution Approach

The solution involves the following steps:

1. Build a Hash Map:
   • Create a dictionary (or map) that links each employee's id to their Employee object. This enables O(1) lookup by id.
2. Traverse the Employee Hierarchy:
   • Start from the given id and use either DFS (recursion or stack) or BFS (queue) to visit each subordinate.
   • At each employee, add their importance to a running total.
   • For each subordinate, recursively or iteratively repeat the process.
3. Return the Total Importance:
   • After visiting all subordinates (direct and indirect), return the computed total.

This approach ensures that each employee is visited exactly once, and lookups are efficient due to the hash map.

Example Walkthrough

Input:

• Employees:
  • Employee(1, 5, [2, 3])
  • Employee(2, 3, [])
  • Employee(3, 3, [])
• id = 1

1. Build a hash map:
   • {1: Employee(1,5,[2,3]), 2: Employee(2,3,[]), 3: Employee(3,3,[])}
2. Start with employee 1:
   • Add 5 to total (total = 5).
   • Visit subordinates 2 and 3.
3. Visit employee 2:
   • Add 3 to total (total = 8).
   • No subordinates.
4. Visit employee 3:
   • Add 3 to total (total = 11).
   • No subordinates.

Result: The total importance is 11.

Code Implementation

# Definition for Employee.
class Employee:
    def __init__(self, id: int, importance: int, subordinates: list):
        self.id = id
        self.importance = importance
        self.subordinates = subordinates

class Solution:
    def getImportance(self, employees: list, id: int) -> int:
        emp_map = {e.id: e for e in employees}
        
        def dfs(emp_id):
            employee = emp_map[emp_id]
            total = employee.importance
            for sub_id in employee.subordinates:
                total += dfs(sub_id)
            return total
        
        return dfs(id)
      

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

class Solution {
public:
    int getImportance(vector<Employee*> employees, int id) {
        unordered_map<int, Employee*> emp_map;
        for (auto e : employees) {
            emp_map[e->id] = e;
        }
        return dfs(id, emp_map);
    }
    
    int dfs(int id, unordered_map<int, Employee*>& emp_map) {
        Employee* emp = emp_map[id];
        int total = emp->importance;
        for (int sub_id : emp->subordinates) {
            total += dfs(sub_id, emp_map);
        }
        return total;
    }
};
      

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

class Solution {
    public int getImportance(List<Employee> employees, int id) {
        Map<Integer, Employee> empMap = new HashMap<>();
        for (Employee e : employees) {
            empMap.put(e.id, e);
        }
        return dfs(id, empMap);
    }
    
    private int dfs(int id, Map<Integer, Employee> empMap) {
        Employee emp = empMap.get(id);
        int total = emp.importance;
        for (int subId : emp.subordinates) {
            total += dfs(subId, empMap);
        }
        return total;
    }
}
      

/**
 * // Definition for Employee.
 * function Employee(id, importance, subordinates) {
 *     this.id = id;
 *     this.importance = importance;
 *     this.subordinates = subordinates;
 * }
 */

/**
 * @param {Employee[]} employees
 * @param {number} id
 * @return {number}
 */
var getImportance = function(employees, id) {
    const empMap = new Map();
    for (let e of employees) {
        empMap.set(e.id, e);
    }

    function dfs(empId) {
        const emp = empMap.get(empId);
        let total = emp.importance;
        for (let subId of emp.subordinates) {
            total += dfs(subId);
        }
        return total;
    }

    return dfs(id);
};
      

Time and Space Complexity

Brute-force Approach:

• If you searched for each subordinate by iterating through the list every time, the worst-case time complexity would be O(N²), where N is the number of employees.
• This is because for each subordinate, you might have to scan the whole list to find the corresponding Employee object.

• Building the hash map takes O(N) time and space.
• Traversing the employee hierarchy visits each employee once, so the DFS/BFS part is O(N).
• Total time complexity: O(N)
• Total space complexity: O(N) (for the hash map and recursion/queue stack)

The optimization comes from using the hash map for O(1) lookups, drastically reducing redundant work.

Summary

The Employee Importance problem is elegantly solved by mapping employee IDs to their objects for fast lookup, and then traversing the hierarchy with DFS or BFS. This ensures each employee is only visited once and makes the solution both simple and efficient. The key insight is to avoid repeated linear searches by using a hash map, which brings the complexity down to O(N). This approach is robust, easy to implement, and highly scalable for large organizations.