Domain 2MediumCORE

Kill Process

We are given a tree structure of processes where each node represents a process ID (pid) and its parent's ID (ppid). The input consists of two arrays: pid containing the current process IDs and ppid containing their respective parents. We need to identify all descendants (including children, grandchildren, etc.) that will be terminated if we kill a specific target process given by kill.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Tree#Queue

582. Kill Process

Model: qwen3.5:9b
Topics: Tree,Queue
FAANG asked: 0
Acceptance rate: 63.9%


Problem Breakdown

We are given a tree structure of processes where each node represents a process ID (pid) and its parent’s ID (ppid). The input consists of two arrays: pid containing the current process IDs and ppid containing their respective parents. We need to identify all descendants (including children, grandchildren, etc.) that will be terminated if we kill a specific target process given by kill.

Key Inputs:

  • Two integer lists pid and ppid of length nn.
  • An integer kill representing the root node ID for our traversal.

Outputs:

  • A list of integers containing all killed processes (the subtree rooted at kill). Order is irrelevant.

Constraints & Edge Cases:

  • Scale: NN up to 50,000. This rules out any nested loops or repeated linear scans (O(N2)O(N^2)). We need an efficient graph traversal approach.
  • Structure: It’s a tree (single parent per node except the root where ppid is 0). No cycles exist.
  • IDs: Process IDs are not necessarily contiguous integers, so we cannot use array indexing for direct lookup; hash maps/dictionaries are required.

Intuition

If I were to solve this naively without preprocessing, finding all children of a process would require iterating through the entire pid list every time to find nodes whose parent matches the current node. If the tree is deep or wide, doing this repeatedly results in O(N2)O(N^2) complexity, which will Time Out (TLE) given the constraints (N=50kN=50k).

The core insight here is that we are dealing with a tree traversal problem. To traverse efficiently from one node to its descendants, I need fast access to “who are my children?”. Since ppid gives us parent-to-child relationships implicitly (by saying process AA has parent BB, it implies AA is a child of BB), we should invert this relationship upfront.

I will build an adjacency list where the key is the Parent ID and the value is a list of Child IDs. Once I have this map, finding all descendants becomes a simple Breadth-First Search (BFS) or Depth-First Search (DFS). Since Python’s recursion limit might be hit with deep trees (N=50kN=50k), an iterative stack-based DFS is safer and just as efficient.

Approach

  1. Build the Graph: Iterate through pid and ppid. For each pair (child, parent), add child to a list associated with parent in a hash map (dictionary). This takes O(N)O(N) time. Note: We ignore entries where parent == 0 because we only care about traversing from the specific kill node downwards; however, storing them doesn’t hurt logic-wise as long as we don’t try to traverse from 0 unless it’s our target (which won’t happen based on constraints).
  2. Traverse: Initialize a result list and a stack/queue with the starting process ID (kill).
  3. Iterate: While the traversal structure is not empty:
    • Pop the current node from the stack.
    • Add it to our results (it’s being killed).
    • Look up its children in our adjacency map and push them onto the stack/queue if they exist.
  4. Return: Return the collected list of IDs.

Complexity Analysis

  • Time Complexity: O(N)O(N). We iterate through pid once to build the graph (NN operations). Then we traverse each node exactly once during BFS/DFS. Total time is linear with respect to input size.
  • Space Complexity: O(N)O(N). The adjacency map stores every edge in the tree, which requires space proportional to NN. Additionally, the stack and result list store up to NN elements in worst-case scenarios (e.g., a line graph).

Solution

from collections import defaultdict
from typing import List

def killProcess(pid: List[int], ppid: List[int], kill: int) -> List[int]:
    # Build adjacency map: Parent ID -> [List of Child IDs]
    children_map = defaultdict(list)
    
    for child, parent in zip(pid, ppid):
        if parent != 0: 
            children_map[parent].append(child)
            
    killed_processes = []
    stack = [kill]
    
    while stack:
        current_pid = stack.pop()
        killed_processes.append(current_pid)
        
        # If this process has children, add them to the traversal queue/stack
        if current_pid in children_map:
            for child_id in children_map[current_pid]:
                stack.append(child_id)
                
    return killed_processes

Edge Cases Handled

  • Single Process: If pid has length 1 and it matches kill, the loop runs once, returns [kill]. Correctly handled by initialization of stack with kill.
  • Kill Root Node (Global): The root is defined as having no parent (ppid=0). Our map logic ignores entries where parent == 0 to save space. If we kill the node that has ppid=0, it will be added to results, and since its children are stored under their respective keys in the map (populated when processing those specific child nodes), traversal continues correctly from there.
  • Deep Tree: Using an iterative stack avoids Python’s default recursion limit (1000 frames) which would crash on a skewed tree of depth > 1000 with recursive DFS.