Employee Importance LeetCode Solution

Difficulty Level Medium
Frequently asked in Amazon Apple Google Microsoft UberViews 2281

Problem Statement

Employee Importance LeetCode Solution – 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 important 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.

Employee Importance LeetCode Solution

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.

Explanation

Thoughts Before Coding

  • The employees are passed in as a list
    • We need to have a quicker lookup of employees using their ID
    • So, we will need to first put all of the employees inside a HashMap for O(1) lookup
  • If we take a closer look the structure is very similar to a tree
    • Each root node can be represented as the leader
    • Each of the children nodes can be represented as subordinates
  • We can use recursion to find the total importance
    • We will first find the importance value of our current node
    • Then we will add this value to the total values accumulated from each of the child nodes

We can consider each employee as a node in the graph and traverse each node that is accessible from the employee id given in the input and track the total importance.

Both DFS and BFS traversal will get accepted as solution. We will be doing DFS (Depth First Search).

Now to find the total importance of an employee, it will be the importance of that employee, plus the total importance of each of that employee’s subordinates. This is a straightforward depth-first search.

Code

Java Code for Employee Importance

class Solution {
    Map<Integer, Employee> emap;
    public int getImportance(List<Employee> employees, int queryid) {
        emap = new HashMap();
        for (Employee e: employees) emap.put(e.id, e);
        return dfs(queryid);
    }
    public int dfs(int eid) {
        Employee employee = emap.get(eid);
        int ans = employee.importance;
        for (Integer subid: employee.subordinates)
            ans += dfs(subid);
        return ans;
    }
}

C++ Code for Employee Importance

class Solution {
public:
    int getImportance(vector<Employee*> employees, int id) {
        unordered_map<int, Employee*> map;
        for(const auto element : employees){   
            map[element->id] = element;
        }   
        return help(map, id);
    }
    int help(unordered_map<int, Employee*>& map, const int id){
        auto sum = map[id]->importance;
        for(const auto element : map[id]->subordinates){ 
            sum += help(map, element);
        }
        return sum;
    }
};

Python Code for Employee Importance

class Solution(object):
    def getImportance(self, employees, query_id):
        emap = {e.id: e for e in employees}
        def dfs(eid):
            employee = emap[eid]
            return (employee.importance +
                    sum(dfs(eid) for eid in employee.subordinates))
        return dfs(query_id)

Complexity Analysis for Employee Importance LeetCode Solution

Time Complexity

O(N) since in the worst case also we will iterate over each node (employee) only once.

Space Complexity

O(N) we use a hashmap to store employee id for easy retrieval.

 

Translate »