# 690. Employee Importance

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2F8hyGU8GcsYjBzYKFnbcP%2F%E5%9C%96%E7%89%87.png?alt=media\&token=a99d8230-b1b1-4694-af1b-72d6386265b7)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FeSX6oJIlcIBvJXMPQBbj%2F%E5%9C%96%E7%89%87.png?alt=media\&token=273efa06-aaeb-4e81-b128-57f0570bfd08)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FiwiI26boHGOeUK1DOyXY%2F%E5%9C%96%E7%89%87.png?alt=media\&token=f7eae083-6991-4e97-8eaf-4d4028d347ee)

```
recursive to add importance

time: O(e*s), e is employees, s is each employees' subordinates
space: O(e*s)
```

```
class Solution {
    int res = 0;
    public int getImportance(List<Employee> employees, int id) {
        for (Employee e : employees) {
            if (e.id == id) {
                calculate(e, employees);
            }
        }
        return res;
    }
    private void calculate(Employee e, List<Employee> employees) {
        res += e.importance;
        if (e.subordinates == null || e.subordinates.size() == 0) {
            return;
        }
        for (Integer sid : e.subordinates) {
            for (Employee se : employees) {
                if (se.id == sid) {
                    calculate(se, employees);
                }
            }
        }
    }
}

/*

recursive to add importance

time: O(e*s), e is employees, s is each employees' subordinates
space: O(e*s)
*/
```



## use HashMap DFS

time: O(n), may cal every Employee

space: O(n)

```java
class Solution {
    public int getImportance(List<Employee> employees, int id) {
        Map<Integer, Employee> emp = new HashMap<>();
        for (Employee e : employees) {
            emp.put(e.id, e);
        }
        return cal(emp, id);
    }
    private int cal(Map<Integer, Employee> emp, int id) {
        Employee e = emp.get(id);
        int total = e.importance;
        
        for (int subId : e.subordinates) {
            total += cal(emp, subId);
        }
        return total;
    }
}
```

or use global variable

```java
class Solution {
    int res = 0;
    public int getImportance(List<Employee> employees, int id) {
        Map<Integer, Employee> emp = new HashMap<>();
        for (Employee e : employees) {
            emp.put(e.id, e);
        }
        cal(emp, id);
        return res;
    }
    private void cal(Map<Integer, Employee> emp, int id) {
        Employee e = emp.get(id);
        res += e.importance;
        if (e.subordinates == null || e.subordinates.size() == 0) {
            return;
        }
        for (int subId : e.subordinates) {
            cal(emp, subId);
        }
    }
}
```



## BFS

我想就認為是 O(n) 吧, n 是全部員工數

```
time: O(e*s), e is employees, s is each employees' subordinates
space: O(e*s)
```

```java
class Solution {
    public int getImportance(List<Employee> employees, int id) {
        Map<Integer, Employee> map = new HashMap<>();
        for (Employee e : employees) {
            map.put(e.id, e);
        }
        
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(id);
        
        int total = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int eid = queue.poll();
                Employee e = map.get(eid); 
                total += e.importance;
                for (int sid : e.subordinates) {
                    queue.offer(sid);
                }
            }
        }
        return total;
    }
    
}
```

or

```java
class Solution {
    public int getImportance(List<Employee> employees, int id) {
        Map<Integer, Employee> map = new HashMap<>();
        for (Employee e : employees) {
            map.put(e.id, e);
        }
        return bfs(map.get(id), map);
        
    }
    private int bfs(Employee e, Map<Integer, Employee> map) {
        int total = 0;
        Queue<Employee> queue = new LinkedList<>();
        queue.offer(e);
        
        while (!queue.isEmpty()) {
            Employee parent = queue.poll();
            total += parent.importance;
            
            for (int id : parent.subordinates) {
                queue.offer(map.get(id));
            }
        }
        return total;
    }
}

```



#### DFS another

```java
/*
// Definition for Employee.
class Employee {
    public int id;
    public int importance;
    public List<Integer> subordinates;
};
*/

class Solution {
    int totalImportance = 0;
    public int getImportance(List<Employee> employees, int id) {
        Map<Integer, Employee> map = new HashMap<>();
        for (Employee e : employees) {
            map.put(e.id, e);
        }
        dfs(map.get(id), map);
        
        return totalImportance;
    }
    private void dfs(Employee e, Map<Integer, Employee> map) {
        if (e == null) {
            return;
        }
        totalImportance += e.importance;
        for (int id : e.subordinates) {
            Employee sub = map.get(id);
            dfs(sub, map);
        }
    }
}


/*
return the total importance value of this employee 
and all their direct and indirect subordinates.


build a map to find Employee data <id, Employee>: T: O(n)

get Employee, List<Integer> subordinates;

T: O(all subordinates.size(), all subtree value)
add this Employee'value, and all subordinates's value (use id to get sub Employee)

T: O(n + all subordinates.size())
s: O(n)
*/
```

or

```java
class Solution {
    public int getImportance(List<Employee> employees, int id) {
        Map<Integer, Employee> map = new HashMap<>();
        for (Employee e : employees) {
            map.put(e.id, e);
        }
        return dfs(map.get(id), map);
        
    }
    private int dfs(Employee e, Map<Integer, Employee> map) {
        if (e == null) {
            return 0;
        }
        int totalImportance = 0;
        totalImportance += e.importance;
        for (int id : e.subordinates) {
            Employee sub = map.get(id);
            totalImportance += dfs(sub, map);
        }
        return totalImportance;
    }
}
```
