# Java O(n) BFS Easy To Understand Solution

• Explanation
The idea for this question is to use BFS to traverse the employee hierarchy, given an initial employee. We first visit the initial employee, then visit the employee's subordinates, and then visit the subordinates' subordinates, and so on, until we reach the bottom of the hierarchy.

Time Complexity
The time complexity is O(n) where n is the number of employees in our input employees, since we traverse through all employees when populating importanceMap, subordinatesMap and possibly all employees when performing BFS.

``````class Solution {
public int getImportance(List<Employee> employees, int id) {
// Maps employee id to the employee's importance value
Map<Integer, Integer> importanceMap = new HashMap<>();

// Maps employee id to employee's list of subordinate ids
Map<Integer, List<Integer>> subordinatesMap = new HashMap<>();

// Populate importanceMap, subordinatesMap for future O(1) lookup
for (Employee employee : employees) {
importanceMap.put(employee.id, employee.importance);
subordinatesMap.put(employee.id, employee.subordinates);
}

int totalImportanceValue = 0;

// We visit the given employee first

// BFS happens here
while (!employeesToVisit.isEmpty()) {
// Retrieve all relevant information about the first employee
int employeeId = employeesToVisit.removeFirst();
int employeeValue = importanceMap.get(employeeId);
List<Integer> subordinates = subordinatesMap.get(employeeId);

// Update our total importance value; append all subordinates
totalImportanceValue += employeeValue;