Java O(n) BFS Easy To Understand Solution


  • 0
    B

    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;
            LinkedList<Integer> employeesToVisit = new LinkedList<>();
            
            // We visit the given employee first
            employeesToVisit.add(id);
            
            // 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;
                employeesToVisit.addAll(subordinates);
            }
            return totalImportanceValue;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.