Python Solution


  • 0
    S
    class Solution(object):
        def getImportance(self, employees, id):
            employees.sort(key=lambda x: x.id)
            res = 0
            subs = [employees[id-1]]
            for sub in subs:
                res += sub.importance
                subs += [employees[x-1]  for x in sub.subordinates ]
            return res
    

    Edited: sort the list first, complexity would be n log(n) + n


  • 0
    I

    @shaynexwang
    nice and tidy


  • 0
    D

    @shaynexwang How can you guarantee that [employees[id-1]] is the location of the first employee? The question does not explicitly say employees will be sorted by id. In fact you cannot even guarantee that employees has enough items to index at [id-1]. The problem does not say that employee ids span 1 to N. If this code passed OJ, I think more test cases need to be added.


  • 0
    S

    @david120 you are right we cannot assume the list is sorted, we do need a better test. I think a non-empty list of Employee is assumed, otherwise you'd get an index error anyway. If the employee list is empty then what should be given as an employee id?


  • 0
    D

    @shaynexwang Yes I think you can assume employees is not empty. But you've also assumed that the employee ids are the same as the indices of the list. For example, your code would not pass

    employees = [ [10,1,[20]], [20, 1, []] ]
    id = 10
    

    because there's no way we can look employees[id-1].


  • 0
    Z

    I actually quit like this one although it can not passes the new test cases and the time complicity is also worse than BFS/DFS. However it gives new ideas.


Log in to reply
 

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