Employee Importance - Leetcode Solution

The Employee Importance problem on Leetcode requires us to calculate the total importance of an employee and all its subordinates recursively.

The problem statement can be summarized as follows:

We are given a list of employees with their IDs, importance, and a list of their subordinates' IDs.

We need to calculate the total importance of a given employee and all its subordinates recursively.

To solve this problem, we can start by creating a hashmap to store the employee's ID and its corresponding Employee object.

We can then iterate through the given list of employees and create an Employee object for each employee.

Next, we can iterate through the list again and add each employee's subordinates to their corresponding Employee object.

Once we have built our hashmap, we can implement a recursive function to calculate the total importance of an employee.

The recursive function will take an employee's ID as input and return the total importance of that employee and all its subordinates.

To implement the recursive function, we can start by getting the Employee object corresponding to the given employee ID.

We can then get the importance of that employee and iterate through its subordinates.

For each subordinate, we can recursively call the function and add its importance to the total.

Finally, we can return the total importance.

Here's the Python code that implements the solution:

class Employee:
    def __init__(self, id: int, importance: int, subordinates: List[int]):
        self.id = id
        self.importance = importance
        self.subordinates = subordinates
        
def getImportance(employees: List[Employee], id: int) -> int:
    # create hashmap to store employees by ID
    employee_map = {}
    for employee in employees:
        employee_map[employee.id] = employee
    
    # recursive function to calculate total importance
    def calculateImportance(id):
        employee = employee_map[id]
        total = employee.importance
        for subordinate_id in employee.subordinates:
            total += calculateImportance(subordinate_id)
        return total
    
    # call recursive function with given employee ID
    return calculateImportance(id)

The time complexity of this solution is O(N), where N is the number of employees in the input list. This is because we need to iterate through the list twice to build the hashmap and call the recursive function for each employee.

The space complexity is also O(N), as we need to store each employee object in the hashmap.

1