# 690. Employee Importance

![](/files/J1n72E7tE40Bk1wzFs3n)

![](/files/fAnfGXFDGXXmumo2NOpM)

![](/files/w4RXww3PQCHRlFwKNWfh)

```
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;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/bfs/690.-employee-importance.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.