Approach: Depth first search
Intuition
For finding the total importance of employee x, we need to find total importance of each subordinate of x.
which can be done in recursive manner. We create a graph from given vector and then use DFS algorithm starting from
the given id. This will give us the required total importance.
C++ Solution  Accepted
class Solution {
public:
//helper function for DFS
int dfs(vector < list <int> > adjlist, int id, vector <int> importance){
int answer = importance[id];
//base case
if(adjlist[id].size() == 0)
return answer;
list<int>::iterator itr;
itr= adjlist[id].begin();
while(itr!=adjlist[id].end()){
//recursive call for all subordinates of current node.
answer+=dfs(adjlist,(*itr),importance);
itr++;
}
return answer;
}
int getImportance(vector<Employee*> employees, int id) {
//creating adjacency list from the vector
vector < list <int> > adjlist(employees.size()+1);
//hash for getting importance
vector <int> importance(employees.size()+1);
for(int i=0;i<employees.size();i++){
importance[employees[i]>id]=employees[i]>importance;
for(int j=0;j<employees[i]>subordinates.size();j++)
adjlist[employees[i]>id].push_back(employees[i]>subordinates[j]);
}
//calling helper function.
int solution = dfs(adjlist,id,importance);
return solution;
}
};
Complexity Analysis

Time complexity : O(n) for DFS.

Space complexity : O(n). We need O(n) space for creating importance vector and for system stack for recursion.