Simple Java Solution using Hashmap and Queue. Beats 95%


  • 0
    R

    Create a Hashmap of each node and its child processes. Add the process to be killed in a queue. Go through all its children and keep adding their child also to the queue until queue is empty.

    Takes O(n) time and O(n) space.

    public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
            List<Integer> result = new ArrayList<>();
            HashMap<Integer, List<Integer>> childList = new HashMap<>();
    
            int size = ppid.size();
            for (int i = 0; i < size; i++) {
                if (childList.containsKey(ppid.get(i))) {
                    List<Integer> newList = childList.get(ppid.get(i));
                    newList.add(pid.get(i));
                    childList.put(ppid.get(i), newList);
                } else {
                    List<Integer> newList = new ArrayList<>();
                    newList.add(pid.get(i));
                    childList.put(ppid.get(i), newList);
                }
            }
            if (childList.get(0).get(0) == kill) { //check if it's a root node. 
                return pid;
            }
    
            LinkedList<Integer> queue = new LinkedList<>();
            queue.add(kill);
            while (!queue.isEmpty()) {
                int key = queue.poll();
                result.add(key);
                if (childList.containsKey(key)) {
                    List<Integer> childNodes = childList.get(key);
                    for (int i = 0; i < childNodes.size(); i++) {
                        queue.add(childNodes.get(i));
                    }
                }
            }
    
            return result;
        }
    

Log in to reply
 

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