solution by akshay_dtu

  • 0

    Approach: Depth first search


    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 {
        //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();
                //recursive call for all subordinates of current node.
            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++){
                for(int j=0;j<employees[i]->subordinates.size();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.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.