{x}
blog image

Employee Importance

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.

 

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.

690. Employee Importance

Description

This problem involves calculating the total importance value of an employee and all their subordinates (direct and indirect). The input is a list of Employee objects, each containing an ID, importance value, and a list of subordinate IDs. The goal is to find the total importance value for a given employee ID.

Solution: Hash Table + Depth-First Search (DFS)

This approach uses a hash table for efficient lookup of employee information and a depth-first search (DFS) to traverse the employee hierarchy.

1. Data Structure:

A hash table (dictionary in Python, HashMap in Java, unordered_map in C++, map in Go and TypeScript) is used to store employee information. The key is the employee ID, and the value is the Employee object. This allows for O(1) lookup time.

2. DFS Algorithm:

The dfs function performs a recursive depth-first search. For each employee:

  • It adds the employee's importance value to the total.
  • It recursively calls dfs for each of the employee's subordinates.
  • The sum of the employee's importance and the importance of all their subordinates is returned.

3. Main Function:

The main function (getImportance) first populates the hash table with employee data. Then, it calls the dfs function starting with the given id. The result of dfs (the total importance) is returned.

Time and Space Complexity Analysis

  • Time Complexity: O(N), where N is the number of employees. This is because in the worst case, we visit each employee exactly once during the DFS traversal.
  • Space Complexity: O(N) in the worst case. This is due to the space used by the hash table to store employee information and the recursive call stack during DFS. The recursive call stack's depth is at most the height of the employee hierarchy, which can be, in the worst case, equal to N.

Code Implementation (Multiple Languages)

The code implementations below demonstrate the solution in various programming languages. They all follow the same fundamental algorithm: building a hash table for fast lookups and using DFS for hierarchical traversal.

Python3

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:
        employee_map = {e.id: e for e in employees}
 
        def dfs(employee_id: int) -> int:
            employee = employee_map[employee_id]
            total_importance = employee.importance
            for subordinate_id in employee.subordinates:
                total_importance += dfs(subordinate_id)
            return total_importance
 
        return dfs(id)

Java

class Employee {
    public int id;
    public int importance;
    public List<Integer> subordinates;
    // Constructor and other methods as needed
}
 
class Solution {
    public int getImportance(List<Employee> employees, int id) {
        Map<Integer, Employee> employeeMap = new HashMap<>();
        for (Employee e : employees) {
            employeeMap.put(e.id, e);
        }
 
        return dfs(employeeMap, id);
    }
 
    private int dfs(Map<Integer, Employee> employeeMap, int employeeId) {
        Employee employee = employeeMap.get(employeeId);
        int totalImportance = employee.importance;
        for (int subordinateId : employee.subordinates) {
            totalImportance += dfs(employeeMap, subordinateId);
        }
        return totalImportance;
    }
}

C++

class Employee {
public:
    int id;
    int importance;
    vector<int> subordinates;
    // Constructor and other methods as needed
};
 
class Solution {
public:
    int getImportance(vector<Employee*> employees, int id) {
        unordered_map<int, Employee*> employeeMap;
        for (Employee* e : employees) {
            employeeMap[e->id] = e;
        }
        return dfs(employeeMap, id);
    }
 
    int dfs(unordered_map<int, Employee*>& employeeMap, int employeeId) {
        Employee* employee = employeeMap[employeeId];
        int totalImportance = employee->importance;
        for (int subordinateId : employee->subordinates) {
            totalImportance += dfs(employeeMap, subordinateId);
        }
        return totalImportance;
    }
};

JavaScript

/**
 * @param {Employee[]} employees
 * @param {number} id
 * @return {number}
 */
var getImportance = function(employees, id) {
    const employeeMap = new Map();
    for (const employee of employees) {
        employeeMap.set(employee.id, employee);
    }
 
    function dfs(employeeId) {
        const employee = employeeMap.get(employeeId);
        let totalImportance = employee.importance;
        for (const subordinateId of employee.subordinates) {
            totalImportance += dfs(subordinateId);
        }
        return totalImportance;
    }
 
    return dfs(id);
};

Go

type Employee struct {
    Id int
    Importance int
    Subordinates []int
}
 
func getImportance(employees []*Employee, id int) int {
    employeeMap := make(map[int]*Employee)
    for _, employee := range employees {
        employeeMap[employee.Id] = employee
    }
 
    var dfs func(int) int
    dfs = func(employeeId int) int {
        employee := employeeMap[employeeId]
        totalImportance := employee.Importance
        for _, subordinateId := range employee.Subordinates {
            totalImportance += dfs(subordinateId)
        }
        return totalImportance
    }
 
    return dfs(id)
}

TypeScript

class Employee {
    id: number;
    importance: number;
    subordinates: number[];
    constructor(id: number, importance: number, subordinates: number[]) {
        this.id = id;
        this.importance = importance;
        this.subordinates = subordinates;
    }
}
 
function getImportance(employees: Employee[], id: number): number {
    const employeeMap = new Map<number, Employee>();
    for (const employee of employees) {
        employeeMap.set(employee.id, employee);
    }
 
    function dfs(employeeId: number): number {
        const employee = employeeMap.get(employeeId)!;
        let totalImportance = employee.importance;
        for (const subordinateId of employee.subordinates) {
            totalImportance += dfs(subordinateId);
        }
        return totalImportance;
    }
 
    return dfs(id);
}

These code examples provide a clear and concise implementation of the solution, highlighting the efficiency gained through the use of a hash table and depth-first search. Remember to adapt the Employee class definition to match the specific requirements of your environment.