Employee Importance

Problem Statement

You are provided with employee data which includes each employee's unique ID, their importance value, and a list of IDs representing their direct subordinates. Using this data structure, you are tasked with computing the total importance value for a specified employee, which includes the importance of the employee themselves alongside the importance values of all their direct and indirect subordinates. This requires traversing through the employee hierarchy to aggregate the importance values, ensuring every subordinate (direct and indirect) is accounted for in the sum.

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

Approach and Intuition

To solve the problem of calculating the total importance value of an employee along with their subordinates, consider the following step-by-step approach:

1. First, convert the list of employees into a more accessible data structure. A dictionary can be useful here where each key would be an employee's ID and the value would be an object containing the employee's importance and their subordinates' IDs.

2. Implement a recursive function to help accumulate the importance values. This function would:

   • Take an employee's ID as an input.
   • Retrieve the corresponding employee's data (importance and subordinates) from the dictionary.
   • Initialize total importance with the employee's own importance.
   • Recursively call the function for each ID in the employee's subordinates list and add the result to the total importance.
   • Return the total importance accumulated.

Now, examining the examples given:

• In Example 1, the request is to evaluate the total importance for employee ID 1. Following the recursive strategy:

  • Start with employee 1 who has an importance value of 5.
  • Employee 1 has two subordinates, IDs 2 and 3, both with an importance of 3.
  • Thus, the total is 5 (own importance) + 3 (from ID 2) + 3 (from ID 3) = 11.

• In Example 2, it queries the importance for employee ID 5, who has no subordinates:

  • Importance is directly taken as -3 as there are no subordinate contributions to add.

This straightforward recursive method ensures that each employee and their hierarchical tree are systematically accounted for, accumulating the importance values as specified. The constraints specify a reasonable limit on the number of employees and their IDs, ensuring that our approach will perform efficiently within the provided limits.

Solutions

class Solution {
    Map<Integer, Employee> employeeMap;
    public int getTotalImportance(List<Employee> employees, int id) {
        employeeMap = new HashMap<>();
        for (Employee e: employees) {
            employeeMap.put(e.id, e);
        }
        return calculateImportance(id);
    }
    public int calculateImportance(int employeeId) {
        Employee currentEmployee = employeeMap.get(employeeId);
        int total = currentEmployee.importance;
        for (Integer subordinateId: currentEmployee.subordinates) {
            total += calculateImportance(subordinateId);
        }
        return total;
    }
}