beat 99.85% python solution


  • 0
    F

    first, fast but not correct theoretically, but can be accepted:

        def getImportance(self, employees, id):
            return employees[id - 1].importance + sum(
                self.getImportance(employees, subordinate_id) for subordinate_id in employees[id - 1].subordinates)
    

    second, correct but slow:

        def getImportance(self, employees, id):
            ddict = {employee.id: employee for employee in employees}
            return ddict[id].importance + sum(
                self.getImportance(employees, subordinate_id) for subordinate_id in ddict[id].subordinates)

  • 0
    A

    @fhqplzj Is this dfs implementation? Can you provide a dfs implementation of the same?


  • 0
    F

    @ash.ps312
    yes, this is the recursive dfs implementation, but can also be rewritten in a non-recursive style using stack


  • 0
    A

    @fhqplzj Cool, thanks


  • 0
    F

    @ash.ps312
    dfs implementation using stack:

        def getImportance(self, employees, id):
            stack, result = [employees[id - 1]], 0
            while stack:
                top_element = stack.pop()
                result += top_element.importance
                for subordinate_id in top_element.subordinates:
                    stack.append(employees[subordinate_id - 1])
            return result
    

    another,

        def getImportance(self, employees, id):
            ddict = {employee.id: employee for employee in employees}
            stack, result = [ddict[id]], 0
            while stack:
                top_element = stack.pop()
                result += top_element.importance
                for subordinate_id in top_element.subordinates:
                    stack.append(ddict[subordinate_id])
            return result

Log in to reply
 

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