Leetcode 0690 Employee Importance

Problem statement

https://leetcode.com/problems/employee-importance/

Solution

Just traverse our graph (which is tree) with dfs and return sum of all values for children.

Complexity

Time and space complexity is O(n).

Code

class Solution:
    def getImportance(self, employees, query_id):
        ids = {e.id: e for e in employees}
        
        def dfs(eid):
            employee = ids[eid]
            return (employee.importance + sum(dfs(eid) for eid in employee.subordinates))
        
        return dfs(query_id)