algoadvance

Leetcode 690. Employee Importance

Problem Statement

You have a data structure representing a company of employees. Each employee has a unique ID, a value representing their importance, and a list of IDs of their direct subordinates. You need to find the total importance value of an employee and all their subordinates.

Example:

Employee info:
[ 
  { "id": 1, "importance": 5, "subordinates": [2, 3] }, 
  { "id": 2, "importance": 3, "subordinates": [] }, 
  { "id": 3, "importance": 3, "subordinates": [] }
]

Given the employee ID 1, the total importance value should be 11.

Note:

1. One employee has at most one direct leader, and may have several subordinates.
2. The maximum number of employees won’t exceed 2000.

Clarifying Questions

1. How should I access the employees’ data? Is it given as a list of objects?
   • Yes, the employee data is given as a list of Employee objects.
2. Is the employee structure given as a pre-defined class?
   • Yes, the structure of the Employee class is predefined. Here it is for reference:

   class Employee {
       public int id;
       public int importance;
       public List<Integer> subordinates;
   }
   

Strategy

1. Data Retrieval: Create a mapping from the employee’s ID to the corresponding Employee object for quick access.
2. Recursive Importance Calculation: Define a recursive function that, given an employee ID, computes the total importance by summing the employee’s own importance and the importance of all their subordinates.
3. Depth-First Search (DFS): Use Depth-First Search to traverse from the given employee to all their subordinates recursively.

Code

Here is the Java implementation of the described approach:

import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Employee {
    public int id;
    public int importance;
    public List<Integer> subordinates;
}

public class Solution {
    
    private Map<Integer, Employee> employeeMap;
    
    public int getImportance(List<Employee> employees, int id) {
        // Create a map from id to Employee object for fast access
        employeeMap = new HashMap<>();
        for (Employee emp : employees) {
            employeeMap.put(emp.id, emp);
        }
        return dfs(id);
    }
    
    private int dfs(int id) {
        Employee emp = employeeMap.get(id);
        int totalImportance = emp.importance;
        for (int subId : emp.subordinates) {
            totalImportance += dfs(subId);
        }
        return totalImportance;
    }
}

Time Complexity

• Time Complexity: The DFS approach ensures that each employee and each subordinate relationship is visited exactly once. Given n total employees, the time complexity is O(n).

• Space Complexity: The space complexity is also O(n) due to the storage required for the hashmap and the system stack during recursive calls.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?