# Kill Process LeetCode Solution

Difficulty Level Medium

## Problem Statement

Kill Process LeetCode Solution – You have `n` processes forming a rooted tree structure. You are given two integer arrays `pid` and `ppid`, where `pid[i]` is the ID of the `i`th process and `ppid[i]` is the ID of the `i`th process’s parent process.

Each process has only one parent process but may have multiple children processes. Only one process has `ppid[i] = 0`, which means this process has no parent process (the root of the tree).

When a process is killed, all of its children processes will also be killed.

Given an integer `kill` representing the ID of a process you want to kill, return a list of the IDs of the processes that will be killed. You may return the answer in any order. ```Input: pid = [1,3,10,5], ppid = [3,0,5,3], kill = 5
Output: [5,10]
Explanation: The processes colored in red are the processes that should be killed.```

## Explanation

we can use a hashmap that stores a particular process value and the list of its direct children.
And then treat it as a tree traversal problem. (BFS/DFS)

or

Construct an adjacency list that maintains the child process linked to that process. Run BFS by starting with the process to be killed. Store all the processes that are killed

## Code

### C++ Code for Kill Process

```class Solution {
public:
vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
vector<int> killed;
map<int, set<int>> children;
for (int i = 0; i < pid.size(); i++) {
children[ppid[i]].insert(pid[i]);
}
killAll(kill, children, killed);
return killed;
}

private:
void killAll(int pid, map<int, set<int>>& children, vector<int>& killed) {
killed.push_back(pid);
for (int child : children[pid]) {
killAll(child, children, killed);
}
}
};```

### Java Code for Kill Process

```public class Solution {
public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
if (kill == 0) return pid;

int n = pid.size();
Map<Integer, Set<Integer>> tree = new HashMap<>();
for (int i = 0; i < n; i++) {
tree.put(pid.get(i), new HashSet<Integer>());
}
for (int i = 0; i < n; i++) {
if (tree.containsKey(ppid.get(i))) {
Set<Integer> children = tree.get(ppid.get(i));
tree.put(ppid.get(i), children);
}
}

List<Integer> result = new ArrayList<>();
traverse(tree, result, kill);

return result;
}

private void traverse(Map<Integer, Set<Integer>> tree, List<Integer> result, int pid) {

Set<Integer> children = tree.get(pid);
for (Integer child : children) {
traverse(tree, result, child);
}
}
}```

### Python Code for Kill Process

```class Solution(object):
def killProcess(self, pid, ppid, kill):
"""
:type pid: List[int]
:type ppid: List[int]
:type kill: int
:rtype: List[int]
"""
myTree = dict()
for i, parent in enumerate(ppid):
myTree[parent] =  myTree.get(parent,[])
myTree[parent].append(pid[i])

res = []
stack = [kill]
while stack:
cur = stack.pop()
res.append(cur)
stack.extend(myTree.get(cur,[]))

return res```

## Complexity Analysis for Kill Process LeetCode Solution

### Time Complexity

O(n+e) since we are doing a bfs traversal.

### Space Complexity

O(n) since we store the nodes in a stack/ array.

Translate »