Sponsored
Sponsored
The problem can be approached by using a Depth-First Search (DFS). The main idea is to accumulate the importance of an employee and all of their direct and indirect subordinates. We use a recursive function to traverse the subordinates of each employee. The base case is when an employee has no subordinates (leaf node). Each recursion step accumulates importance from the current employee and proceeds to accumulate from its subordinates.
Time Complexity: O(N), where N is the number of employees, as each employee is visited once.
Space Complexity: O(N), due to the recursion stack and storage in the map for employees.
1class Employee:
2 def __init__(self, id: int, importance: int, subordinates: list):
3 self.id = id
4 self.importance = importance
5 self.subordinates = subordinates
6
7class Solution:
8 def getImportance(self, employees: list, id: int) -> int:
9 employee_map = {e.id: e for e in employees}
10 def dfs(emp_id: int) -> int:
11 employee = employee_map[emp_id]
12 return employee.importance + sum(dfs(sub_id) for sub_id in employee.subordinates)
13 return dfs(id)This Python solution defines a recursive dfs function that fetches an employee from a map (created for fast lookup) and calculates their total importance including their subordinates recursively.
An alternative method involves using Breadth-First Search (BFS). In this approach, a queue is used to iteratively explore each level of employee hierarchy starting from the given employee ID. One processes each employee by summing their importance and enqueuing their subordinates. This technique assures visiting all employees in a breadth-wise manner and eventually collecting the cumulative importance value.
Time Complexity: O(N), as it processes each employee once.
Space Complexity: O(N), due to the queue and employee mapping storage.
1using System.Collections.Generic;
2
class Employee {
public int id;
public int importance;
public IList<int> subordinates;
}
class Solution {
public int GetImportance(IList<Employee> employees, int id) {
var employeeMap = new Dictionary<int, Employee>();
foreach (var e in employees) {
employeeMap[e.id] = e;
}
var queue = new Queue<int>();
queue.Enqueue(id);
int totalImportance = 0;
while (queue.Count > 0) {
int currentId = queue.Dequeue();
var employee = employeeMap[currentId];
totalImportance += employee.importance;
foreach (var subId in employee.subordinates) {
queue.Enqueue(subId);
}
}
return totalImportance;
}
}The C# solution employs a breadth-first traversal through a queue. As employees are dequeued, their importance is summed, and their subordinates are enqueued.