[JAVA] Use hashmap for marking (-1:not exist, kill:exist, other:parent) / T : O(N), S : O(N)


  • 0
    J
    class Solution {
        public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
            HashMap<Integer, Integer> map = new HashMap<Integer,Integer>();
            List<Integer> result = new ArrayList<Integer>();
            for(int i = 0; i < pid.size(); i++){
                map.put(pid.get(i), ppid.get(i));
            }
            
            for(int i = 0; i < pid.size(); i++){
                if(search(map, pid.get(i), kill)) result.add(pid.get(i));
            }
                    
            return result;
        }
        
        public boolean search(HashMap<Integer, Integer> map, int pid, int kill){
            if(pid == 0 || map.get(pid) == -1)
                return false;
            if(pid == kill)
                return true;
            
            int parent = map.get(pid);
            map.put(pid, -1);
            if(search(map, parent, kill)){
                map.put(pid, kill);
                return true;
            }
            
            return false;
        }
    }
    

Log in to reply
 

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