3-liner Python Solution (beats 99%)


  • 4

    Simply convert the employees array/list into a map for easy lookup and then do a DFS traversal from the "root" employee node.

    - Yangshun

    class Solution(object):
        def getImportance(self, employees, id):
            """
            :type employees: Employee
            :type id: int
            :rtype: int
            """
            # Time: O(n)
            # Space: O(n)
            emps = {employee.id: employee for employee in employees}
            dfs = lambda id: sum([dfs(sub_id) for sub_id in emps[id].subordinates]) + emps[id].importance
            return dfs(id)         
    

    If you wanna make it more readable, it is 5-lines:

    class Solution(object):
        def getImportance(self, employees, id):
            """
            :type employees: Employee
            :type id: int
            :rtype: int
            """
            # Time: O(n)
            # Space: O(n)
            emps = {employee.id: employee for employee in employees}
            def dfs(id):
                subordinates_importance = sum([dfs(sub_id) for sub_id in emps[id].subordinates])
                return subordinates_importance + emps[id].importance
            return dfs(id)
    

  • 2

    The sum doesn't need [ ]'s, without them it is syntactic sugar for a generator.


  • 1

    @awice Cool I never knew about that, thanks for the tip!


Log in to reply
 

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