582. Kill Process - Solution & Explanation

The problem

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.

Example 1:

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.

Example 2:

Input: pid = [1], ppid = [0], kill = 1
Output: [1]

Constraints:

n == pid.length
n == ppid.length
1 <= n <= 5 * 10⁴
1 <= pid[i] <= 5 * 10⁴
0 <= ppid[i] <= 5 * 10⁴
Only one process has no parent.
All the values of pid are unique.
kill is guaranteed to be in pid.

Approach overview

Problem Overview: You are given two arrays pid and ppid representing process IDs and their parent process IDs. When a process is killed, every descendant process in that subtree must also terminate. Given a process ID kill, return all processes that will be terminated.

Approach 1: Repeated Parent Scan (Brute Force) (Time: O(n^2), Space: O(n))

A straightforward method repeatedly scans the ppid array to find children of the process being killed. Start with the target kill process in a queue or list. For each process removed, iterate through the entire ppid array to find entries whose parent matches it, then add those child processes to the queue. Continue until no new processes are discovered.

This approach works because the parent-child relationships form a tree. However, each time you discover a node you scan the entire list again, which leads to O(n^2) time in the worst case. The space complexity remains O(n) to store the result and traversal queue. It demonstrates the basic relationship between parent and child processes but becomes inefficient for large inputs.

Approach 2: Build Process Tree + DFS (Time: O(n), Space: O(n))

A more efficient solution builds an adjacency list that maps each parent process to its children. Iterate once through pid and ppid, storing relationships in a HashMap<parent, List<children>>. This transforms the process hierarchy into a tree-like graph structure.

Once the adjacency list is ready, run a traversal starting from the process to kill. A recursive or iterative Depth-First Search walks through every descendant. Add the current node to the result list, then recursively visit each child found in the adjacency list. Because each process is visited at most once, the traversal runs in O(n) time.

This solution relies on constant-time lookups from a Hash Table and a graph traversal over the process tree. The total space complexity is O(n) for the adjacency list and recursion stack. The same structure can also be traversed using Breadth-First Search with a queue if you prefer iterative logic.

Recommended for interviews: The adjacency list + DFS approach is the expected solution. Interviewers want to see that you recognize the parent-child structure as a tree and convert it into a graph representation before traversal. Mentioning the brute-force scan shows baseline reasoning, but implementing the O(n) DFS or BFS traversal demonstrates stronger algorithmic thinking.

Solution

We first construct a graph g based on pid and ppid, where g[i] represents all child processes of process i. Then, starting from the process kill, we perform depth-first search to obtain all killed processes.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of processes.

Python

class Solution:
    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:
        def dfs(i: int):
            ans.append(i)
            for j in g[i]:
                dfs(j)

        g = defaultdict(list)
        for i, p in zip(pid, ppid):
            g[p].append(i)
        ans = []
        dfs(kill)
        return ans

Java

class Solution {
    private Map<Integer, List<Integer>> g = new HashMap<>();
    private List<Integer> ans = new ArrayList<>();

    public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
        int n = pid.size();
        for (int i = 0; i < n; ++i) {
            g.computeIfAbsent(ppid.get(i), k -> new ArrayList<>()).add(pid.get(i));
        }
        dfs(kill);
        return ans;
    }

    private void dfs(int i) {
        ans.add(i);
        for (int j : g.getOrDefault(i, Collections.emptyList())) {
            dfs(j);
        }
    }
}

C++

class Solution {
public:
    vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
        unordered_map<int, vector<int>> g;
        int n = pid.size();
        for (int i = 0; i < n; ++i) {
            g[ppid[i]].push_back(pid[i]);
        }
        vector<int> ans;
        function<void(int)> dfs = [&](int i) {
            ans.push_back(i);
            for (int j : g[i]) {
                dfs(j);
            }
        };
        dfs(kill);
        return ans;
    }
};

TypeScript

function killProcess(pid: number[], ppid: number[], kill: number): number[] {
    const g: Map<number, number[]> = new Map();
    for (let i = 0; i < pid.length; ++i) {
        if (!g.has(ppid[i])) {
            g.set(ppid[i], []);
        }
        g.get(ppid[i])?.push(pid[i]);
    }
    const ans: number[] = [];
    const dfs = (i: number) => {
        ans.push(i);
        for (const j of g.get(i) ?? []) {
            dfs(j);
        }
    };
    dfs(kill);
    return ans;
}

func killProcess(pid []int, ppid []int, kill int) (ans []int) {
	g := map[int][]int{}
	for i, p := range ppid {
		g[p] = append(g[p], pid[i])
	}
	var dfs func(int)
	dfs = func(i int) {
		ans = append(ans, i)
		for _, j := range g[i] {
			dfs(j)
		}
	}
	dfs(kill)
	return
}

Rust

use std::collections::HashMap;

impl Solution {
    pub fn kill_process(pid: Vec<i32>, ppid: Vec<i32>, kill: i32) -> Vec<i32> {
        let mut g: HashMap<i32, Vec<i32>> = HashMap::new();
        let mut ans: Vec<i32> = Vec::new();

        let n = pid.len();
        for i in 0..n {
            g.entry(ppid[i]).or_insert(Vec::new()).push(pid[i]);
        }

        Self::dfs(&mut ans, &g, kill);
        ans
    }

    fn dfs(ans: &mut Vec<i32>, g: &HashMap<i32, Vec<i32>>, i: i32) {
        ans.push(i);
        if let Some(children) = g.get(&i) {
            for &j in children {
                Self::dfs(ans, g, j);
            }
        }
    }
}

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
Repeated Parent Scan (Brute Force)	O(n^2)	O(n)	Small inputs or quick prototype without building extra structures
Adjacency List + DFS	O(n)	O(n)	General optimal solution for tree traversal problems
Adjacency List + BFS	O(n)	O(n)	Iterative alternative when avoiding recursion depth limits

Frequently asked questions

Is Kill Process easy or hard?

Kill Process is generally rated Medium difficulty. The main challenge is recognizing that the pid and ppid arrays describe a tree structure and converting them into an adjacency list before performing DFS or BFS.

Kill Process Python/Java solution

Most solutions build a dictionary or HashMap mapping parent IDs to child lists, then run DFS from the kill ID. The traversal collects each visited process into the result list. This implementation works consistently across Python, Java, C++, Go, TypeScript, and Rust.

How to solve Kill Process in O(n)?

First create a hash map mapping each parent process ID to a list of its child processes by iterating through the pid and ppid arrays once. Then run a DFS or BFS starting from the given kill process and collect every reachable node. Each node is processed once, giving O(n) total time.

What is the best approach for Kill Process?

The optimal approach builds a parent-to-children adjacency list and performs a DFS or BFS traversal starting from the process to kill. Each process is visited once, giving O(n) time complexity and O(n) space for the map and traversal structure.

Is Kill Process asked at Google/Amazon/Meta?

Kill Process is a common tree or graph traversal interview question seen in companies like Amazon and other large tech firms. It tests whether you can convert parent-child relationships into an adjacency structure and traverse it efficiently.

What data structure is used in Kill Process?

The main data structure is a hash map that stores a parent process ID mapped to a list of its child processes. After building this structure, a DFS recursion stack or BFS queue is used to traverse the process tree.

What is the time complexity of Kill Process?

The optimal solution runs in O(n) time because each process ID is inserted into a hash map once and visited once during the DFS or BFS traversal. Space complexity is also O(n) due to storing the adjacency list and the recursion stack or queue.

Kill Process solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Kill Process solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems