LeetCode 582: Kill Process

Problem Restatement

We are given a list of process IDs and their parent process IDs.

Each process forms part of a process tree.

If a process is killed, then all of its child processes are also killed recursively.

Given a process ID called kill, return all process IDs that will be terminated.

The result may be returned in any order. The official problem defines:

pid[i]  = process ID
ppid[i] = parent process ID of pid[i]

and guarantees that exactly one process has parent 0, which is the root process. (github.com)

Input and Output

Constraints:

Examples

Example 1:

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

The process tree is:

3
├── 1
└── 5
    └── 10

If we kill process 5, then process 10 is also terminated.

Output:

[5, 10]

Example 2:

pid = [1]
ppid = [0]
kill = 1

Output:

[1]

There is only one process.

First Thought: Scan Repeatedly

One idea is:

1. Start with the kill process.
2. Scan all processes.
3. If a process has a killed parent, mark it as killed.
4. Repeat until no new process is added.

This works, but repeated scanning is inefficient.

If there are many processes, we may scan the full list many times.

Key Insight

The process structure is a tree.

Each process points to its parent:

child -> parent

But for traversal, we want the reverse direction:

parent -> list of children

So we first build an adjacency list.

For example:

pid  = [1, 3, 10, 5]
ppid = [3, 0, 5, 3]

becomes:

{
    3: [1, 5],
    5: [10]
}

Then starting from kill, we perform DFS or BFS to visit all descendants.

Every visited node is a killed process.

Algorithm

1. Build a hash map:

parent -> children

2. For every process:

   • Add pid[i] to the child list of ppid[i].

3. Start DFS or BFS from kill.

4. Add each visited process to the result.

5. Visit all children recursively.

6. Return the collected processes.

Correctness

The adjacency list stores exactly the children of every process.

The traversal starts from the process kill. Therefore, the killed process itself is always included in the result.

Whenever the traversal visits a process, it recursively visits all of its children from the adjacency list. Since every child process is directly connected to its parent, every descendant of kill is eventually reached.

Processes outside the subtree of kill are never visited because there is no traversal path from kill to those nodes.

Thus, the traversal visits exactly the processes that must be terminated.

Complexity

Let:

n = number of processes

Implementation

from collections import defaultdict

class Solution:
    def killProcess(
        self,
        pid: list[int],
        ppid: list[int],
        kill: int,
    ) -> list[int]:
        children = defaultdict(list)

        for child, parent in zip(pid, ppid):
            children[parent].append(child)

        result = []

        def dfs(process: int) -> None:
            result.append(process)

            for child in children[process]:
                dfs(child)

        dfs(kill)

        return result

Code Explanation

This creates the adjacency list:

children = defaultdict(list)

Each key is a parent process.

Each value is the list of child processes.

This loop builds the graph:

for child, parent in zip(pid, ppid):
    children[parent].append(child)

For example:

parent = 3
child = 5

creates:

children[3] = [5]

The DFS function visits one process:

def dfs(process):

First we record the process:

result.append(process)

Then recursively visit all children:

for child in children[process]:
    dfs(child)

Finally:

dfs(kill)

starts the traversal from the process that must be terminated.

BFS Alternative

A breadth-first solution also works.

from collections import defaultdict, deque

class Solution:
    def killProcess(
        self,
        pid: list[int],
        ppid: list[int],
        kill: int,
    ) -> list[int]:
        children = defaultdict(list)

        for child, parent in zip(pid, ppid):
            children[parent].append(child)

        queue = deque([kill])
        result = []

        while queue:
            process = queue.popleft()
            result.append(process)

            for child in children[process]:
                queue.append(child)

        return result

DFS and BFS both visit exactly the same subtree.

Testing

def run_tests():
    s = Solution()

    assert sorted(
        s.killProcess(
            [1, 3, 10, 5],
            [3, 0, 5, 3],
            5,
        )
    ) == [5, 10]

    assert sorted(
        s.killProcess(
            [1],
            [0],
            1,
        )
    ) == [1]

    assert sorted(
        s.killProcess(
            [1, 2, 3, 4, 5],
            [0, 1, 1, 2, 2],
            2,
        )
    ) == [2, 4, 5]

    assert sorted(
        s.killProcess(
            [1, 2, 3],
            [0, 1, 2],
            1,
        )
    ) == [1, 2, 3]

    print("all tests passed")

run_tests()

Test meaning: