---
tags: leetcode
---

# [690. Employee Importance](https://leetcode.com/problems/employee-importance/)
---
# My Solution
## Solution 1: DFS and unordered map
### The Key Idea for Solving This Coding Question
### C++ Code

/*
// Definition for Employee.
class Employee {
public:
    int id;
    int importance;
    vector<int> subordinates;
};
*/

class Solution {
public:
    int getImportance(vector<Employee *> &employees, int id) {
        unordered_map<int, Employee *> idToEmployee;
        for (int i = 0; i < employees.size(); ++i) {
            idToEmployee[employees[i]->id] = employees[i];
        }

        return dfs(employees, idToEmployee, id);
    }

private:
    int dfs(vector<Employee *> &employees, unordered_map<int, Employee *> &idToEmployee, int currId) {
        Employee *curr = idToEmployee[currId];
        if (curr->subordinates.empty()) {
            return curr->importance;
        }

        int total = curr->importance;
        for (auto &nextId : curr->subordinates) {
            total += dfs(employees, idToEmployee, nextId);
        }

        return total;
    }
};

### Time Complexity
$O(n)$
* $n$ is the number of employees.
### Space Complexity
$O(H)$
* $H$ is the height of the tree.
## Solution 2: DFS and linear search
### The Key Idea for Solving This Coding Question
### C++ Code

/*
// Definition for Employee.
class Employee {
public:
    int id;
    int importance;
    vector<int> subordinates;
};
*/

class Solution {
public:
    int getImportance(vector<Employee*> employees, int id) {
        Employee *curr = findEmployeeById(employees, id);
        if (curr == nullptr) {
            return 0;
        }

        return dfs(employees, curr);
    }

public:
    Employee *findEmployeeById(vector<Employee*> &employees, int id) {
        for (int i = 0; i < employees.size(); ++i) {
            if (employees[i]->id == id) {
                return employees[i];
            }
        }
        return nullptr;
    }

    int dfs(vector<Employee*> &employees, Employee *curr) {
        if (curr == nullptr) {
            return 0;
        }
        if (curr->subordinates.empty()) {
            return curr->importance;
        }

        int importance = curr->importance;
        for (int i = 0; i < curr->subordinates.size(); ++i) {
            Employee *next = findEmployeeById(employees, curr->subordinates[i]);
            if (next == nullptr) {
                continue;
            }

            importance += dfs(employees, next);
        }
        return importance;
    }
};

### Time Complexity
$O(n)$
* $n$ is the number of employees.
### Space Complexity
$O(H)$
* $H$ is the height of the tree.
## Solution 3: BFS
### The Key Idea for Solving This Coding Question
### C++ Code

/*
// Definition for Employee.
class Employee {
public:
    int id;
    int importance;
    vector<int> subordinates;
};
*/

class Solution {
public:
    int getImportance(vector<Employee*> employees, int id) {
        unordered_map<int, Employee*> idToEmployee;
        for (Employee *employee : employees) {
            idToEmployee[employee->id] = employee;
        }
        
        queue<int> q;
        int totalImportance = idToEmployee[id]->importance;
        
        q.push(id);
        while (!q.empty()) {
            int currId = q.front();
            Employee *currEmployee = idToEmployee[currId];
            q.pop();
            
            for (int &nextId : currEmployee->subordinates) {
                Employee *nextEmployee = idToEmployee[nextId];
                
                q.push(nextId);
                totalImportance += nextEmployee->importance;
            }
        }
        
        return totalImportance;
    }
};

### Time Complexity
$O(n)$
* $n$ is the number of employees.
### Space Complexity
$O(n)$
# Miscellane
<!--
# Test Cases

[[1,5,[2,3]],[2,3,[]],[3,3,[]]]
1

[[1,2,[5]],[5,-3,[]]]
5

[[1,5,[2,3]],[2,3,[4,6]],[3,3,[8,10,12]],[4,5,[]],[6,7,[]],[8,9,[]],[10,11,[]],[12,13,[]]]
1

[[1,5,[2,3]],[2,3,[4,6]],[3,3,[8,10,12]],[4,5,[]],[6,7,[]],[8,9,[]],[10,11,[]],[12,13,[]]]
3

-->