Kill Process

How it works

BFS offers an alternative to DFS for traversing the process tree. Instead of going deep into one branch before backtracking, BFS processes all children at the current level before moving to the next. Both approaches yield the same result but BFS can be more intuitive when thinking about the spread of the kill signal.

Steps

1. Build a hash map mapping each parent process ID to its children.
2. Initialize a queue with the kill process.
3. While the queue is not empty:
   • Dequeue a process and add it to the result.
   • Enqueue all of its children.
4. Return the result containing all killed processes.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Where n is the length of the pid and ppid.

Things to watch for

Forgetting to Include the Kill Process Itself

A common mistake is only collecting the children of the process to kill, but forgetting to include the kill process itself in the result. The killed process must be added to the result list before traversing its descendants.

Not Handling Processes With No Children

When building the parent-to-children map, some processes may have no children (leaf processes). Failing to check if a key exists in the map before accessing its children can cause null pointer exceptions or key errors. Always verify the map contains the key before iterating over children.

Using Linear Search for Each Recursive Call

The brute force approach scans the entire ppid array for each recursive call, leading to O(n^2) complexity. This becomes a problem for large inputs. Building a hash map upfront to store parent-child relationships reduces this to O(n) by providing O(1) child lookups.

from typing import List
from collections import deque

class Solution:
    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:
        map_dict = {}
        for i in range(len(ppid)):
            if ppid[i] > 0:
                if ppid[i] not in map_dict:
                    map_dict[ppid[i]] = []
                map_dict[ppid[i]].append(pid[i])

        queue = deque([kill])
        result = []
        while queue:
            r = queue.popleft()
            result.append(r)
            if r in map_dict:
                for child_id in map_dict[r]:
                    queue.append(child_id)

        return result

class Solution {
public:
    vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
        unordered_map<int, vector<int>> map;
        for (int i = 0; i < ppid.size(); i++) {
            if (ppid[i] > 0) {
                map[ppid[i]].push_back(pid[i]);
            }
        }

        queue<int> q;
        vector<int> result;
        q.push(kill);
        while (!q.empty()) {
            int r = q.front();
            q.pop();
            result.push_back(r);
            if (map.find(r) != map.end()) {
                for (int child_id : map[r]) {
                    q.push(child_id);
                }
            }
        }

        return result;
    }
};