⚡Flashcard Drill➔
NeetCode #605LC-582MediumGraphsNC Algo100
← Back to All Problems

#605 · #582 · Kill Process(杀掉进程)

📌 Problem Statement & Constraints

You are given pid (process ids), ppid (parent ids, 0 means no parent) and kill (the process to kill). When a process is killed, all its descendants are killed too. Return the ids of the killed processes in any order. Constraints: 1 <= pid.length <= 5 * 10^4, 1 <= pid[i] <= 5 * 10^4.

💡 Core Algorithmic Approaches

  1. Build a children map from the parent array, then collect the subtree rooted at kill.
  2. The children map is essential: the ppid array gives the parent of each process, so it must be inverted.
  3. A BFS/DFS from the kill target collects all descendants.
  4. ppid == 0 marks the roots, which have no parent.

💻 Benchmark Python3 Implementation

class Solution:
    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:
        from collections import defaultdict, deque
        children = defaultdict(list)
        for c, p in zip(pid, ppid):
            if p != 0:
                children[p].append(c)
        res = []
        q = deque([kill])
        while q:
            node = q.popleft()
            res.append(node)
            q.extend(children[node])
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each process is visited once.
💾 Space Complexity
O(n) for the children map.

⚠️ Interview Pitfalls & Follow-ups

  • Skipping the p != 0 check: the root has no parent, so adding it under key 0 is harmless but unnecessary.
  • Returning only the direct children: the kill propagates through the whole subtree.
  • Searching the ppid array repeatedly: O(n) per lookup; the inverted map makes it O(1).
  • Assuming the process ids are contiguous: they are arbitrary.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems