690. 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