C++ O(N) Hash table and BFS


  • 0
    A
    class Solution {
    public:
        vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
        
            // Maps each process to its children
            unordered_map<int, vector<int>> children_of_each_process;
            for (int i=0; i<ppid.size(); ++i) {
                children_of_each_process[ppid[i]].push_back(pid[i]);
            }
        
            vector<int> processes_killed;
        
            queue<int> processes_to_kill;
            processes_to_kill.push(kill);
        
            while (!processes_to_kill.empty()) {
                int process = processes_to_kill.front();
                processes_to_kill.pop();
            
                processes_killed.push_back(process);
            
                // Find the children of the process, if any, and add them to the queue
                auto it = children_of_each_process.find(process);
                if (it != children_of_each_process.end()) {
                    vector<int> children_of_process = it->second;
                    for (int i=0; i<children_of_process.size(); ++i) {
                        processes_to_kill.push(children_of_process[i]);
                    }
                }
            }
            return processes_killed;
        }
    };

Log in to reply
 

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