Scale Engineer

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 SearchBreadth-First Search
Data structures
ArrayHash TableTree
Companies
RipplingRobinhood

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 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.

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

  1. Initialize totalImportance to 0.
  2. Create a queue (e.g., LinkedList) and add the starting id to it.
  3. 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.
  4. 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.

/*// Definition for Employee.class Employee {    public int id;    public int importance;    public List<Integer> subordinates;};*/class Solution {    public int getImportance(List<Employee> employees, int id) {        int totalImportance = 0;        Queue<Integer> queue = new LinkedList<>();        queue.offer(id);         while (!queue.isEmpty()) {            int currentId = queue.poll();            // Inefficiently find the employee by iterating through the list            for (Employee emp : employees) {                if (emp.id == currentId) {                    totalImportance += emp.importance;                    for (int subordinateId : emp.subordinates) {                        queue.offer(subordinateId);                    }                    break; // Found the employee, can break inner loop                }            }        }        return totalImportance;    }}

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.

Solutions

/* // 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 ; } }

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 →

Next problem