Employee Importance

Med

#0644Time: O(N*K), where N is the total number of employees and K is the number of employees in the hierarchy of the given `id`. The traversal visits K employees, and for each one, it scans the list of N employees. In the worst case, K=N, leading to O(N^2).Space: O(N), where N is the total number of employees. In the worst case, the queue could hold up to N-1 subordinates.2 companies

Algorithms

Depth-First Search Breadth-First Search

Data structures

Array Hash Table Tree

Companies

Rippling Robinhood

Prompt

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 i^th employee.
employees[i].importance is the importance value of the i^th employee.
employees[i].subordinates is a list of the IDs of the direct subordinates of the i^th 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.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly traverses the employee hierarchy starting from the given ID. For each employee encountered during the traversal, it performs a linear search through the entire input list to find their details. This method avoids any preprocessing but results in a significant performance penalty due to the repeated searches.

Algorithm

Initialize totalImportance to 0.
Create a queue (e.g., LinkedList) and add the starting id to it.
Loop while the queue is not empty: a. Dequeue an employeeId. b. Iterate through the entire employees list to find the Employee object whose id matches employeeId. c. Once found, add the employee's importance to totalImportance. d. Add all of the employee's subordinates to the queue. e. Break the inner loop and continue to the next ID in the queue.
After the loop finishes, return totalImportance.

Walkthrough

In this brute-force method, we use a queue to perform a Breadth-First Search (BFS) starting with the initial employee ID. We initialize a running total for the importance value. In a loop, we process one employee ID from the queue at a time. The core inefficiency lies in how we retrieve employee details: for each ID, we must iterate through the entire employees list to find the matching Employee object. Once the employee is found, we add their importance to our total and add all their subordinate IDs to the queue for future processing. This continues until the queue is empty, meaning we have visited the initial employee and all their direct and indirect subordinates.

1/*2// Definition for Employee.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        int totalImportance = 0;12        Queue<Integer> queue = new LinkedList<>();13        queue.offer(id);14 15        while (!queue.isEmpty()) {16            int currentId = queue.poll();17            // Inefficiently find the employee by iterating through the list18            for (Employee emp : employees) {19                if (emp.id == currentId) {20                    totalImportance += emp.importance;21                    for (int subordinateId : emp.subordinates) {22                        queue.offer(subordinateId);23                    }24                    break; // Found the employee, can break inner loop25                }26            }27        }28        return totalImportance;29    }30}

Complexity

Time

O(N*K), where N is the total number of employees and K is the number of employees in the hierarchy of the given `id`. The traversal visits K employees, and for each one, it scans the list of N employees. In the worst case, K=N, leading to O(N^2).

Space

O(N), where N is the total number of employees. In the worst case, the queue could hold up to N-1 subordinates.

Trade-offs

Pros

Simple to conceptualize without complex data structures.
Uses minimal extra space besides the queue for traversal.

Cons

Extremely inefficient for larger inputs, with a time complexity of O(N^2) in the worst case.
Performs a lot of redundant work by repeatedly scanning the entire list of employees.

This approach significantly optimizes the traversal by first preprocessing the employee list into a HashMap. This map allows for constant-time O(1) lookups of any employee by their ID. After this one-time setup, a standard Breadth-First Search (BFS) is performed to traverse the hierarchy and sum the importance values efficiently.

Algorithm

Create a HashMap<Integer, Employee> to map employee IDs to Employee objects.
Iterate through the input employees list once to populate the map. This provides O(1) lookup time for any employee.
Initialize totalImportance = 0.
Create a Queue<Integer> and add the initial id.
While the queue is not empty: a. Dequeue an employeeId. b. Get the corresponding Employee object from the HashMap in O(1) time. c. Add the employee's importance to totalImportance. d. For each subordinateId in the employee's subordinates list, enqueue it.
Return totalImportance.

Walkthrough

The key to this efficient approach is the preprocessing step. We create a HashMap where keys are employee IDs and values are the Employee objects themselves. We iterate through the input employees list just once to populate this map. This step takes O(N) time, where N is the number of employees.

With the map ready, we can find any employee's data in O(1) time. We then use a Queue to perform a BFS traversal, starting with the initial id. We initialize totalImportance to 0. While the queue is not empty, we dequeue an employee ID, use our map to instantly retrieve their Employee object, add their importance to the total, and enqueue all their subordinate IDs. This process ensures that every employee in the specified hierarchy is visited exactly once, leading to a linear time complexity.

1/*2// Definition for Employee.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        for (Employee emp : employees) {13            empMap.put(emp.id, emp);14        }15 16        int totalImportance = 0;17        Queue<Integer> queue = new LinkedList<>();18        queue.offer(id);19 20        while (!queue.isEmpty()) {21            int currentId = queue.poll();22            Employee currentEmp = empMap.get(currentId);23            totalImportance += currentEmp.importance;24            for (int subordinateId : currentEmp.subordinates) {25                queue.offer(subordinateId);26            }27        }28        return totalImportance;29    }30}

Complexity

Time

O(N), where N is the total number of employees. It takes O(N) to build the map and O(K) for the BFS traversal (where K is the number of employees in the subtree, K <= N). The total time complexity is dominated by O(N).

Space

O(N), where N is the total number of employees. This space is used for the HashMap and the queue. The queue's maximum size can be O(N) in the case of a very wide hierarchy.

Trade-offs

Pros

Highly efficient with a linear time complexity of O(N).
The iterative nature of BFS avoids the risk of stack overflow errors that can occur with deep recursion.

Cons

Requires extra space of O(N) to store the HashMap.

This approach also uses a HashMap for efficient O(1) employee lookups, but it employs a Depth-First Search (DFS) traversal instead of BFS. DFS explores as far as possible down one branch before backtracking. This is naturally implemented using recursion, which can lead to very clean and concise code.

Algorithm

Create a HashMap<Integer, Employee> and populate it from the employees list for O(1) lookups.
Define a recursive helper function, let's call it dfs(employeeId).
The main function calls dfs(id) with the starting employee ID and returns the result.
The dfs(employeeId) function works as follows: a. Look up the Employee object for the current employeeId in the HashMap. b. Initialize a local variable importanceSum with the current employee's importance. c. Iterate through the subordinates list of the current employee. d. For each subordinateId, make a recursive call dfs(subordinateId) and add the returned value to importanceSum. e. Return importanceSum.

Walkthrough

Similar to the BFS approach, the first step is to build a HashMap that maps employee IDs to Employee objects. This O(N) preprocessing step is crucial for efficiency.

Once the map is built, we use a recursive helper function to perform the DFS. The function, say dfs(employeeId), calculates the total importance for the subtree rooted at employeeId. It does this by first getting the importance of the employeeId itself. Then, it iterates through all direct subordinates and makes a recursive call for each one. The sum of the results from these recursive calls is added to the current employee's importance. The base case for the recursion is an employee with no subordinates, where the function simply returns that employee's own importance.

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

Complexity

Time

O(N), where N is the total number of employees. O(N) for building the map and O(K) for the DFS traversal (where K is the number of employees in the subtree, K <= N). The total time complexity is O(N).

Space

O(N). O(N) is used for the HashMap. The recursion call stack also uses space, which is proportional to the depth of the hierarchy, H. In the worst-case scenario of a skewed tree, H can be N, leading to O(N) space complexity.

Trade-offs

Pros

Efficient with O(N) time complexity.
The recursive solution is often very elegant, concise, and easy to understand.

Cons

Requires O(N) extra space for the HashMap.
The recursive implementation can lead to a StackOverflowError if the employee hierarchy is very deep (i.e., a tall and skinny tree structure).

Solutions

Solution

1/* // Definition for Employee. class Employee { public int id; public int importance; public List<Integer> subordinates; }; */ class Solution { private final Map < Integer , Employee > map = new HashMap <>(); public int getImportance ( List < Employee > employees , int id ) { for ( Employee employee : employees ) { map . put ( employee . id , employee ); } return dfs ( id ); } private int dfs ( int id ) { Employee employee = map . get ( id ); int sum = employee . importance ; for ( Integer subordinate : employee . subordinates ) { sum += dfs ( subordinate ); } return sum ; } }

1/** * Definition for Employee. * function Employee(id, importance, subordinates) { * this.id = id; * this.importance = importance; * this.subordinates = subordinates; * } */ /** * @param {Employee[]} employees * @param {number} id * @return {number} */ var GetImportance =2  function (employees, id) {3    const map = new Map();4    for (const employee of employees) {5      map.set(employee.id, employee);6    }7    const dfs = (id) => {8      const employee = map.get(id);9      let sum = employee.importance;10      for (const subId of employee.subordinates) {11        sum += dfs(subId);12      }13      return sum;14    };15    return dfs(id);16  };

1/* // Definition for Employee. class Employee { public: int id; int importance; vector<int> subordinates; }; */ class Solution { public: int getImportance ( vector < Employee *> employees , int id ) { unordered_map < int , Employee *> d ; for ( auto & e : employees ) { d [ e -> id ] = e ; } function < int ( int ) > dfs = [ & ]( int i ) -> int { int s = d [ i ] -> importance ; for ( int j : d [ i ] -> subordinates ) { s += dfs ( j ); } return s ; }; return dfs ( id ); } };

1""" # Definition for Employee. 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 : m = { emp . id : emp for emp in employees } def dfs ( id : int ) -> int : emp = m [ id ] s = emp . importance for sub in emp . subordinates : s += dfs ( sub ) return s return dfs ( id )

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1/* // Definition for Employee. class Employee { public int id; public int importance; public List<Integer> subordinates; }; */ class Solution { private final Map < Integer , Employee > map = new HashMap <>(); public int getImportance ( List < Employee > employees , int id ) { for ( Employee employee : employees ) { map . put ( employee . id , employee ); } return dfs ( id ); } private int dfs ( int id ) { Employee employee = map . get ( id ); int sum = employee . importance ; for ( Integer subordinate : employee . subordinates ) { sum += dfs ( subordinate ); } return sum ; } }

1/** * Definition for Employee. * function Employee(id, importance, subordinates) { * this.id = id; * this.importance = importance; * this.subordinates = subordinates; * } */ /** * @param {Employee[]} employees * @param {number} id * @return {number} */ var GetImportance =2  function (employees, id) {3    const map = new Map();4    for (const employee of employees) {5      map.set(employee.id, employee);6    }7    const dfs = (id) => {8      const employee = map.get(id);9      let sum = employee.importance;10      for (const subId of employee.subordinates) {11        sum += dfs(subId);12      }13      return sum;14    };15    return dfs(id);16  };

1/* // Definition for Employee. class Employee { public: int id; int importance; vector<int> subordinates; }; */ class Solution { public: int getImportance ( vector < Employee *> employees , int id ) { unordered_map < int , Employee *> d ; for ( auto & e : employees ) { d [ e -> id ] = e ; } function < int ( int ) > dfs = [ & ]( int i ) -> int { int s = d [ i ] -> importance ; for ( int j : d [ i ] -> subordinates ) { s += dfs ( j ); } return s ; }; return dfs ( id ); } };

1""" # Definition for Employee. 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 : m = { emp . id : emp for emp in employees } def dfs ( id : int ) -> int : emp = m [ id ] s = emp . importance for sub in emp . subordinates : s += dfs ( sub ) return s return dfs ( id )

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.