Java DFS O(n) Time O(n) Space


  • 10
    public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
        
        // Store process tree as an adjacency list
        Map<Integer, List<Integer>> adjacencyLists = new HashMap<>();
        for (int i=0;i<ppid.size();i++) {
            adjacencyLists.putIfAbsent(ppid.get(i), new LinkedList<>());
            adjacencyLists.get(ppid.get(i)).add(pid.get(i));
        }
        
        // Kill all processes in the subtree rooted at process "kill"
        List<Integer> res = new LinkedList<>();
        Stack<Integer> stack = new Stack<>();
        stack.add(kill);
        while (!stack.isEmpty()) {
            int cur = stack.pop();
            res.add(cur);
            List<Integer> adjacencyList = adjacencyLists.get(cur);
            if (adjacencyList == null) continue;
            stack.addAll(adjacencyList);
        }
        return res;   
    
    }
    

  • 15
    Y

    Same idea, queue's used instead of stack. (By the way, Stack is not recommended to use...)

    public class Solution {
        public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
            Map<Integer, List<Integer>> map = new HashMap<>();
            for (int i = 0; i < pid.size(); ++i) {
                map.putIfAbsent(ppid.get(i), new ArrayList<>());
                map.get(ppid.get(i)).add(pid.get(i));
            }
            List<Integer> ans = new ArrayList<>();
            Queue<Integer> q = new ArrayDeque<>();
            q.add(kill);
            while (!q.isEmpty()) {
                int n = q.poll();
                ans.add(n);
                if (map.containsKey(n)) {
                    q.addAll(map.get(n));
                }
            }
            return ans;
        }
    }
    

  • 0
    J

    @yl May I ask why you said "stack is not recommended to use"? thank you for answering.


  • 4
    Y

    @jameslee0623 You can refer to this: https://docs.oracle.com/javase/8/docs/api/java/util/Stack.html
    It says: "A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class."

    The major problem with it I think is it is a class instead of an interface.


  • 0
    K

    @yl Thanks for ur sharing.


  • 0
    P

    Same idea using recursion instead of using Stack:

            public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
    		Map<Integer, List<Integer>> map = new HashMap<>();
    		for (int i = 0; i < ppid.size(); i++) {
    			map.putIfAbsent(ppid.get(i), new ArrayList<>());
    			map.get(ppid.get(i)).add(pid.get(i));
    		}
    		List<Integer> res = new ArrayList<>();
    		return killProcess(kill, res, map);
    	}
    
    	public List<Integer> killProcess(int kill, List<Integer> res, Map<Integer, List<Integer>> map) {
    		res.add(kill);
    		for (int pid : map.getOrDefault(kill, new ArrayList<>())) {
    			killProcess(pid, res, map);
    		}
    		return res;
    	}
    

  • 0

    I think this is BFS or level order traversal instead of DFS


  • 0
    Y

    great solution.
    DFS version.

        private Map<Integer, List<Integer>> next = null;  // children map
        public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
            next = new HashMap<>();
            
            for (int i = 0; i < pid.size(); ++i) {
                int parent = ppid.get(i);
                int child = pid.get(i);
                List<Integer> childList = null;
                if (!next.containsKey(parent)) {
                    childList = new ArrayList<>();
                    next.put(parent, childList);
                }
                else childList = next.get(parent);
                
                childList.add(child);
            }
            
            List<Integer> res = new ArrayList<>();
            dfs(kill, res);
            
            return res;
        }    
        
        
        private void dfs(int id, List<Integer> path) {
            path.add(id); 
            
            if (!next.containsKey(id))   return; // leaf, no children
            for (int cid : next.get(id)) dfs(cid, path);
        }
    

  • 0
    Y

    @piyush121 see my dfs version..


  • 0
    F

    Same idea but using queue. BFS version.

    public class Solution {
        public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
            List<Integer> result = new ArrayList<>();
            Queue<Integer> queue = new LinkedList<>();
            HashMap<Integer,List<Integer>> map  = new HashMap<>();
            for(int i = 0;i<pid.size();i++){
                int par = ppid.get(i);
                if(!map.containsKey(par)){
                    map.put(par,new ArrayList());
                }
                map.get(par).add(pid.get(i));
            }
            queue.add(kill);
            while(!queue.isEmpty()){
                int par = queue.poll();
                List<Integer> child = map.get(par);
                if(child != null)
                    for(int i = 0;i<child.size();i++)
                        queue.add(child.get(i));
                result.add(par);
            }
            return result;
        }
    }
    

  • 0
    S

    By adding the following line, improvised the run time by a big margin

    if (ppid.get(pid.indexOf(kill)) == 0) return pid;
    

  • 0
    S

    slightly different solution without stacks or queues for storing pid to be killed.

    public  List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
            if(ppid.size() <= 0 || pid.size() <= 0){
                return new ArrayList<>();
            }
         
            Map<Integer, Set<Integer>> processMap = new HashMap<>();
            for(int i = 0; i < ppid.size(); i++){
                Set<Integer> v = processMap.getOrDefault(ppid.get(i), new TreeSet<>());
                v.add(pid.get(i));
                processMap.put(ppid.get(i), v);
            }
            List<Integer> killList = new ArrayList<>();
            killList.add(kill);
            int i = 0;
            while(i < killList.size()){
                killList.addAll(processMap.getOrDefault(killList.get(i),  new TreeSet<>()));
                i++;
            }
            return killList;
        }
    

Log in to reply
 

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