Leetcode 690. Employee Importance

Problem Explanation:

You are given employee data in the form of an array where each entry represents an employee using three fields: employee's id, importance value, and list of ids of their direct subordinates. Your task is to calculate the total importance value of an employee including the importance of their subordinates. This is a hierarchical relationship where an employee could have many subordinates and their importance would add up to contribute to their manager. The implementation thus revolves around Depth-First Search (DFS) algorithm.

Let's take an example for employee 1 with importance 5 and two direct subordinates, 2 and 3 with importance 3 each. The data would be like [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]]. The total importance value of employee 1 would be 5 (own importance) + 3 (importance of employee 2) + 3 (importance of employee 3) = 11.

Solution Approach:

The given problem hinges on the idea of DFS for traversing through employee hierarchy. The strategy here is to convert the list of employees into a dictionary where employee id is the key and corresponding employee data is the value. This dictionary will make it easier to locate any employee by their id while performing DFS.

During the DFS, the process starts from the root employee and recursively traverses through each of the child employees i.e. direct subordinates. The importance of each traversed employee is added up to get the total sum.

Python Solution

1
2
3class Employee:
4    def __init__(self, id: int, importance: int, subordinates: list[int]):
5        self.id=id
6        self.importance=importance
7        self.subordinates=subordinates
8
9class Solution:
10    def getImportance(self, employees, id: int) -> int:
11        emp_map = {emp.id: emp for emp in employees}
12
13        def dfs(id):
14            return emp_map[id].importance + sum(dfs(sub_id) for sub_id in emp_map[id].subordinates)
15
16        return dfs(id)

Java Solution

1
2java
3class Employee {
4    public int id;
5    public int importance;
6    public List<Integer> subordinates;
7}
8
9class Solution {
10    public int getImportance(List<Employee> employees, int id) {
11        Map<Integer, Employee> empMap = new HashMap<>();
12        
13        for (Employee emp : employees) { 
14            empMap.put(emp.id, emp);
15        }
16        
17        return dfs(id, empMap);
18    }
19
20    private int dfs(int id, Map<Integer, Employee> empMap) {
21        Employee employee = empMap.get(id);
22        int tot = employee.importance;
23
24        for (int subId : employee.subordinates) {
25            tot += dfs(subId, empMap);
26        }
27        
28        return tot;
29    }
30}

In both the Python and Java solutions, first, we make a dictionary (in Python) or Map (in Java) to create a direct mapping from each employee id to its corresponding employee object. Then we perform a depth-first search starting from the employee id given in the problem and add up the importance value of all the employees we visit.## JavaScript Solution

1
2javascript
3function Employee(id, importance, subordinates) {
4    this.id = id;
5    this.importance = importance;
6    this.subordinates = subordinates;
7};
8
9let getImportance = function(employees, id) {
10    let empMap = new Map();
11
12    for(let emp of employees){
13        empMap.set(emp.id, emp);
14    }
15
16    return dfs(id, empMap);
17};
18
19let dfs = function(id, empMap){
20    let employee = empMap.get(id);
21    let total = employee.importance;
22
23    for (let subId of employee.subordinates) {
24        total += dfs(subId, empMap);
25    }
26
27    return total;
28}

In the JavaScript solution, we start off by defining an Employee class constructor function to mimic a similar structure used in Python or Java. Following that, we define a getImportance function which will be executed on our employees array to compute and return the total importance of an employee and all their subordinates.

Inside getImportance, we create a Map object named empMap to create a direct mapping from each employee id to the corresponding employee object, similar to our other solutions.

We then call our dfs helper function, passing it our target employee id and the empMap. This function will enter a depth-first search, add up the importance values of the target employee and all their subordinates, and return this total.

Each of these solutions (Python, Java, and JavaScript) implements the same basic logic to solve the problem. By doing the problem in multiple languages, we can learn how to use fundamental data structures and algorithms in different programming paradigms.