Kill Process

You are given two lists of integers and an integer representing a process id to kill. One of the lists represents a list of process ids and the other represents a list of each of the processes' corresponding (by index) parent ids. When a process is killed, all of its children should also be killed. Return a list of all the process ids that are killed as a result of killing the requested process.

Example(s)

Example 1:

Input: pid = [2, 4, 3, 7], ppid = [0, 2, 2, 3], kill = 3

Process tree:
           2
         /   \
        4     3
             /
            7

Output: [3, 7]
Explanation:
Killing process 3 also kills its child process 7.

Example 2:

Input: pid = [1, 3, 10, 5], ppid = [3, 0, 5, 3], kill = 5

Process tree:
           3
         /   \
        1     5
             /
            10

Output: [5, 10]
Explanation:
Killing process 5 also kills its child process 10.

Example 3:

Input: pid = [1, 2, 3], ppid = [0, 1, 1], kill = 1

Process tree:
           1
         /   \
        2     3

Output: [1, 2, 3]
Explanation:
Killing process 1 also kills its children processes 2 and 3.

Solution

The solution uses tree traversal with DFS/BFS:

1. Build tree: Create a map from parent to children
2. Find descendants: Use DFS/BFS to find all descendants of the target process
3. Include target: Add the target process itself to the result
4. Return list: Return all processes that need to be killed

JavaScript Solution

JavaScript Solution - DFS

/**
* Find all processes to kill (including children)
* @param {number[]} pid - List of process IDs
* @param {number[]} ppid - List of parent process IDs
* @param {number} kill - Process ID to kill
* @return {number[]} - List of all process IDs to kill
*/
function killProcess(pid, ppid, kill) {
// Build tree: map parent -> children
const childrenMap = new Map();

for (let i = 0; i < pid.length; i++) {
  const parent = ppid[i];
  const child = pid[i];
  
  if (!childrenMap.has(parent)) {
    childrenMap.set(parent, []);
  }
  childrenMap.get(parent).push(child);
}

const result = [];

/**
 * DFS to collect all descendants
 * @param {number} processId - Current process ID
 */
function dfs(processId) {
  // Add current process to result
  result.push(processId);
  
  // Recursively kill all children
  if (childrenMap.has(processId)) {
    for (const child of childrenMap.get(processId)) {
      dfs(child);
    }
  }
}

// Start DFS from the process to kill
dfs(kill);

return result;
}

// Test cases
console.log('Example 1:', killProcess([2, 4, 3, 7], [0, 2, 2, 3], 3)); 
// [3, 7]

console.log('Example 2:', killProcess([1, 3, 10, 5], [3, 0, 5, 3], 5)); 
// [5, 10]

console.log('Example 3:', killProcess([1, 2, 3], [0, 1, 1], 1)); 
// [1, 2, 3]

Output:

Click "Run Code" to execute the code and see the results.

Python Solution

Python Solution - DFS

from typing import List
from collections import defaultdict

def kill_process(pid: List[int], ppid: List[int], kill: int) -> List[int]:
  """
  Find all processes to kill (including children)
  
  Args:
      pid: List of process IDs
      ppid: List of parent process IDs
      kill: Process ID to kill
      
  Returns:
      List[int]: List of all process IDs to kill
  """
  # Build tree: map parent -> children
  children_map = defaultdict(list)
  
  for i in range(len(pid)):
      parent = ppid[i]
      child = pid[i]
      children_map[parent].append(child)
  
  result = []
  
  def dfs(process_id: int):
      """
      DFS to collect all descendants
      """
      # Add current process to result
      result.append(process_id)
      
      # Recursively kill all children
      for child in children_map[process_id]:
          dfs(child)
  
  # Start DFS from the process to kill
  dfs(kill)
  
  return result

# Test cases
print('Example 1:', kill_process([2, 4, 3, 7], [0, 2, 2, 3], 3))  
# [3, 7]

print('Example 2:', kill_process([1, 3, 10, 5], [3, 0, 5, 3], 5))  
# [5, 10]

print('Example 3:', kill_process([1, 2, 3], [0, 1, 1], 1))  
# [1, 2, 3]

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Alternative Solution (BFS)

Here's a BFS version:

JavaScript BFS

/**
 * BFS approach
 */
function killProcessBFS(pid, ppid, kill) {
  // Build tree: map parent -> children
  const childrenMap = new Map();
  
  for (let i = 0; i < pid.length; i++) {
    const parent = ppid[i];
    const child = pid[i];
    
    if (!childrenMap.has(parent)) {
      childrenMap.set(parent, []);
    }
    childrenMap.get(parent).push(child);
  }
  
  const result = [];
  const queue = [kill];
  
  while (queue.length > 0) {
    const processId = queue.shift();
    result.push(processId);
    
    // Add all children to queue
    if (childrenMap.has(processId)) {
      for (const child of childrenMap.get(processId)) {
        queue.push(child);
      }
    }
  }
  
  return result;
}

Python BFS

from collections import deque, defaultdict

def kill_process_bfs(pid: List[int], ppid: List[int], kill: int) -> List[int]:
    """
    BFS approach
    """
    # Build tree: map parent -> children
    children_map = defaultdict(list)
    
    for i in range(len(pid)):
        parent = ppid[i]
        child = pid[i]
        children_map[parent].append(child)
    
    result = []
    queue = deque([kill])
    
    while queue:
        process_id = queue.popleft()
        result.append(process_id)
        
        # Add all children to queue
        for child in children_map[process_id]:
            queue.append(child)
    
    return result

Complexity

• Time Complexity: O(n) - Where n is the number of processes. We build the tree in O(n) and traverse it in O(n).
• Space Complexity: O(n) - For the children map and recursion stack/queue.

Approach

The solution uses tree traversal with DFS/BFS:

1. Build tree:

   • Create a map from parent process ID to list of children
   • For each process, add it to its parent's children list

2. Find descendants:

   • Start from the target process to kill
   • Use DFS/BFS to traverse all descendants

3. Collect processes:

   • Add the target process itself
   • Add all its descendants (children, grandchildren, etc.)

4. Return result:

   • Return list of all processes to kill

Key Insights

• Tree structure: Processes form a tree with parent-child relationships
• Build adjacency list: Map parent to children for efficient traversal
• DFS/BFS: Both work to find all descendants
• Include target: Don't forget to include the target process itself
• O(n) time: Must process all processes

Step-by-Step Example

Let's trace through Example 1: pid = [2, 4, 3, 7], ppid = [0, 2, 2, 3], kill = 3

Step 1: Build tree
  Process 2: parent = 0 → childrenMap[0] = [2]
  Process 4: parent = 2 → childrenMap[2] = [4]
  Process 3: parent = 2 → childrenMap[2] = [4, 3]
  Process 7: parent = 3 → childrenMap[3] = [7]
  
  childrenMap = {
    0: [2],
    2: [4, 3],
    3: [7]
  }

Step 2: DFS from kill = 3
  dfs(3):
    result.push(3) → result = [3]
    childrenMap.has(3)? Yes, children = [7]
    dfs(7):
      result.push(7) → result = [3, 7]
      childrenMap.has(7)? No
      return
    return
  
  Result: [3, 7]

Visual Representation

Example 1: pid = [2, 4, 3, 7], ppid = [0, 2, 2, 3], kill = 3

Process tree:
           2 (root, parent=0)
         /   \
        4     3 (kill this)
             /
            7 (child of 3)

Killing process 3:
  - Process 3 itself ✓
  - Process 7 (child of 3) ✓
  
Result: [3, 7]

Example 3: pid = [1, 2, 3], ppid = [0, 1, 1], kill = 1

Process tree:
           1 (kill this)
         /   \
        2     3 (children of 1)

Killing process 1:
  - Process 1 itself ✓
  - Process 2 (child of 1) ✓
  - Process 3 (child of 1) ✓
  
Result: [1, 2, 3]

Edge Cases

• Kill root: Kills entire tree
• Kill leaf: Only kills that process
• Single process: Returns [processId]
• No children: Returns just the target process
• Deep tree: Works correctly with any depth
• Wide tree: Works correctly with many children

Important Notes

• Tree structure: Processes form a tree, not a general graph
• Parent-child relationship: Each process has one parent (except root)
• Include target: Must include the process being killed
• Cascade kill: All descendants must be killed
• O(n) time: Must process all processes in worst case

Why Tree Traversal Works

Key insight:

• Processes form a tree structure
• Killing a process requires killing all its descendants
• DFS/BFS naturally finds all descendants
• Building parent->children map enables efficient traversal

Related Problems

• All Nodes Distance K in Binary Tree: Different tree problem
• Delete Nodes and Return Forest: Different tree deletion
• Serialize and Deserialize N-ary Tree: Different problem
• N-ary Tree Level Order Traversal: Different traversal

Takeaways

• Build tree structure from parent-child relationships
• DFS/BFS finds all descendants efficiently
• Include target process in the result
• O(n) time to build tree and traverse
• Tree traversal is the key technique