Java recursive O(N) clean solution


  • 0
    A

    Simple and clean implementation time: O(N) space O(N)

    1. Store mapping from parent to child
    2. Kill current process and all child
        public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
    
            Map<Integer, List<Integer>> parentToChild = new HashMap<>();
    
            for(int i = 0; i < pid.size(); i ++){
                if(!parentToChild.containsKey(ppid.get(i))) {
                    parentToChild.put(ppid.get(i), new ArrayList<>());
                }
                parentToChild.get(ppid.get(i)).add(pid.get(i));
            }
    
            List<Integer> killedProcesses = new ArrayList<>();
            kill(parentToChild, kill, killedProcesses);
            return killedProcesses;
        }
    
        private void kill(Map<Integer, List<Integer>> parentToChild, int processToKill,
                          List<Integer> killedProcesses){
    
            killedProcesses.add(processToKill);
            if(parentToChild.get(processToKill) != null) {
                for (Integer childProcess : parentToChild.get(processToKill)) {
                    kill(parentToChild, childProcess, killedProcesses);
                }
            }
        }
    

Log in to reply
 

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