LeetCode 582: Kill Process Solution in Python – A Step-by-Step Guide

What Is LeetCode 582: Kill Process?

In LeetCode 582: Kill Process, you’re given two lists: pid, a list of process IDs, and ppid, a list of corresponding parent process IDs, along with an integer kill representing the process ID to terminate. Your task is to return a list of all process IDs that will be killed, including kill and all its child processes (direct and indirect descendants) in the process tree. For example, with pid = [1, 3, 10, 5], ppid = [3, 0, 5, 3], and kill = 5, the result is [5, 10] because process 5’s child is 10. This problem builds on LeetCode 199: Binary Tree Right Side View for tree traversal but applies it to a general tree structure represented as parent-child relationships.

Problem Statement

• Input: pid (List[int])—list of process IDs; ppid (List[int])—list of parent process IDs; kill (int)—process ID to kill.
• Output: List[int]—list of process IDs to be killed (including kill and descendants).
• Rules: Each process has one parent (0 if root); kill process and all children recursively.

Constraints

• 1 <= pid.length <= 5 * 10⁴
• pid.length == ppid.length
• 1 <= pid[i] <= 5 * 10⁴
• 0 <= ppid[i] <= 5 * 10⁴
• kill is in pid
• All pid[i] are distinct

Examples

• Input: pid = [1,3,10,5], ppid = [3,0,5,3], kill = 5
• Output: [5,10]
• Tree: 0 → 3 → (1, 5 → 10); killing 5 kills 10.
• Input: pid = [1,3,10,5], ppid = [3,0,5,3], kill = 3
• Output: [3,1,5,10]
• Killing 3 kills 1, 5, and 5’s child 10.
• Input: pid = [1], ppid = [0], kill = 1
• Output: [1]
• Single process, no children.

Understanding the Problem: Killing Processes

To solve LeetCode 582: Kill Process in Python, we need to identify all processes to kill starting from a given kill ID, including its entire subtree in a process hierarchy defined by pid and ppid, handling up to 5 * 10⁴ processes efficiently. A brute-force approach checking each process repeatedly (O(n²)) could work but would be slow. Instead, building an adjacency list and using DFS or BFS traverses the tree in O(n) time, leveraging the graph-like structure of parent-child relationships. We’ll explore:

• Best Solution (DFS with Adjacency List): O(n) time, O(n) space—fast and optimal (n = number of processes).
• Alternative Solution (BFS with Queue): O(n) time, O(n) space—effective and iterative.

Let’s dive into the DFS solution with a friendly breakdown!

Best Solution: DFS with Adjacency List

Why DFS Wins

The DFS with adjacency list solution is the best for LeetCode 582 because it efficiently kills all descendant processes in O(n) time and O(n) space by constructing a graph representation from pid and ppid in one pass, then using depth-first search to traverse from the kill node, collecting all reachable processes recursively. It’s like following a family tree from a single ancestor, marking everyone to terminate—all in a swift, recursive sweep!

How It Works

Think of this as a process-killing strategist:

• Step 1: Build Adjacency List:
• Create a dictionary mapping each pid to a list of its child pids using ppid.
• Step 2: Define DFS Function:
• Start at kill, recursively visit all children, add to result.
• Step 3: Execute DFS:
• Call DFS from kill, collect all processes to kill.
• Step 4: Return Result:
• List of process IDs to terminate.
• Why It Works:
• Adjacency list enables O(1) child lookups.
• DFS ensures all descendants are visited exactly once.

It’s like a process-termination maestro!

Step-by-Step Example

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

• Step 1: Build adjacency list:
• graph = {0: [3], 3: [1, 5], 5: [10], 1: [], 10: []}.
• Step 2: DFS from 5:
• Visit 5, add 5.
• Children of 5: [10].
• Visit 10, add 10, no children.
• Step 3: Result: [5, 10].
• Result: [5, 10].

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

• Step 1: graph = {0: [3], 3: [1, 5], 5: [10], 1: [], 10: []}.
• Step 2: DFS from 3:
• Visit 3, add 3.
• Children: [1, 5].
• Visit 1, add 1, no children.
• Visit 5, add 5.
• Children of 5: [10], visit 10, add 10.
• Step 3: Result: [3, 1, 5, 10].
• Result: [3, 1, 5, 10].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

Copy codeclass Solution:
    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:
        # Step 1: Build adjacency list
        graph = {}
        for process_id in pid:
            graph[process_id] = []  # Initialize all PIDs as potential parents
        for child, parent in zip(pid, ppid):
            if parent != 0:  # Skip root (no parent)
                graph[parent].append(child)

        # Step 2: DFS to collect all processes to kill
        def dfs(node: int, result: List[int]):
            result.append(node)  # Add current process
            for child in graph[node]:
                dfs(child, result)  # Recurse on children

        # Step 3: Execute DFS from kill process
        result = []
        dfs(kill, result)

        # Step 4: Return list of processes to kill
        return result

• Lines 5-10: Build graph:
• Initialize all PIDs as keys with empty child lists.
• Map each child to its parent (skip root with ppid 0).
• Lines 13-16: DFS function:
• Add current node to result.
• Recursively visit all children.
• Lines 19-20: Start DFS from kill, collect results.
• Line 23: Return list of killed processes.
• Time Complexity: O(n)—each process visited once.
• Space Complexity: O(n)—graph and result storage.

It’s like a process-killing sleuth!

Alternative Solution: BFS with Queue

Why an Alternative Approach?

The BFS with queue solution uses breadth-first search to traverse the process tree iteratively, running in O(n) time and O(n) space, collecting all processes to kill level-by-level using a queue. It’s effective and avoids recursion, making it a good alternative for those preferring iteration or managing stack space.

How It Works

Picture this as a process-killing queue master:

• Step 1: Build adjacency list from pid and ppid.
• Step 2: Initialize queue with kill process.
• Step 3: BFS:
• Dequeue process, add to result, enqueue its children.
• Repeat until queue empty.
• Step 4: Return result list.

It’s like a level-by-level terminator!

Step-by-Step Example

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

• Step 1: graph = {0: [3], 3: [1, 5], 5: [10], 1: [], 10: []}.
• Step 2: Queue = [5], result = [].
• Step 3: BFS:
• Dequeue 5, result = [5], enqueue [10].
• Dequeue 10, result = [5, 10], no children.
• Step 4: Result: [5, 10].
• Result: [5, 10].

Code for BFS Approach

Copy codefrom collections import deque

class Solution:
    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:
        # Step 1: Build adjacency list
        graph = {}
        for process_id in pid:
            graph[process_id] = []
        for child, parent in zip(pid, ppid):
            if parent != 0:
                graph[parent].append(child)

        # Step 2: BFS with queue
        result = []
        queue = deque([kill])
        while queue:
            curr = queue.popleft()
            result.append(curr)
            for child in graph[curr]:
                queue.append(child)

        # Step 3: Return result
        return result

• Lines 6-11: Build graph same as DFS.
• Lines 14-20: BFS:
• Start queue with kill.
• Dequeue, add to result, enqueue children.
• Line 23: Return list.
• Time Complexity: O(n)—each process visited once.
• Space Complexity: O(n)—queue and result storage.

It’s a queue-based terminator!

Comparing the Two Solutions

• DFS (Best):
• Pros: O(n), O(n), elegant recursion.
• Cons: Stack space for deep trees.
• BFS (Alternative):
• Pros: O(n), O(n), iterative.
• Cons: Slightly more code.

DFS wins for elegance!

Additional Examples and Edge Cases

• Single process: Just kill.
• No children: Single ID.
• Deep tree: Full traversal.

DFS handles them all!

Complexity Recap

• DFS: Time O(n), Space O(n).
• BFS: Time O(n), Space O(n).

DFS’s the elegance champ!

Key Takeaways

• DFS: Tree traversal—learn at Python Basics!
• BFS: Queue power.
• Processes: Killing is fun.
• Python: DFS or BFS, your pick!

Final Thoughts: Terminate Those Processes!

LeetCode 582: Kill Process in Python is a clever graph challenge. DFS with adjacency list is your fast track, while BFS offers an iterative twist. Want more? Try LeetCode 199: Binary Tree Right Side View or LeetCode 207: Course Schedule. Ready to kill? Head to Solve LeetCode 582 on LeetCode and shut down those processes today!