MediumNo. 0582LeetCode Premium
Kill Process — LeetCode 582 Python Solution
- Pattern
- Tree Traversal
- Topics
- Tree, Depth-First Search, Breadth-First Search, Array, Hash Table
- Reading time
- 2 min
- Source
- leetcode.com
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 ith process and ppid[i] is the ID of the ith process's parent process.
Example
- 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.
Python solution
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 ansComplexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Tree Traversal
Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 582. Kill Process is filed here because LeetCode tags it Tree, which is the vocabulary this hub collects.
The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0690 | Employee Importance | Medium |
| 1993 | Operations on Tree | Medium |
| 2368 | Reachable Nodes With Restrictions | Medium |
| 0653 | Two Sum IV - Input is a BST | Easy |
| 0721 | Accounts Merge | Medium |
| 0839 | Similar String Groups | Hard |
Frequently asked questions
- How hard is LeetCode 582. Kill Process?
LeetCode 582. Kill Process is rated Medium on LeetCode.
- What is the time complexity of LeetCode 582. Kill Process?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 582. Kill Process?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 582. Kill Process cover?
LeetCode 582. Kill Process is tagged Tree, Depth-First Search, Breadth-First Search, Array and Hash Table on LeetCode.
- Is LeetCode 582. Kill Process a premium problem?
Yes. LeetCode 582. Kill Process is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.