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
- Build a children map from the parent array, then collect the subtree rooted at
kill. - The children map is essential: the
ppidarray gives the parent of each process, so it must be inverted. - A BFS/DFS from the kill target collects all descendants.
ppid == 0marks 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 != 0check: 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
ppidarray 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.