582. Kill Process 🔒

DifficultyMedium

Description

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 i^th process and ppid[i] is the ID of the i^th process's parent process.

Each process has only one parent process but may have multiple children processes. Only one process has ppid[i] = 0, which means this process has no parent process (the root of the tree).

When a process is killed, all of its children processes will also be killed.

Given an integer kill representing the ID of a process you want to kill, return a list of the IDs of the processes that will be killed. You may return the answer in any order.

Example 1:

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.

Example 2:

Input: pid = [1], ppid = [0], kill = 1
Output: [1]

Constraints:

n == pid.length
n == ppid.length
1 <= n <= 5 * 10⁴
1 <= pid[i] <= 5 * 10⁴
0 <= ppid[i] <= 5 * 10⁴
Only one process has no parent.
All the values of pid are unique.
kill is guaranteed to be in pid.

Solutions

Solution 1: DFS

Thinking

Killing a process kills its whole descendant tree. The parent arrays should become an adjacency list first.

\(g[p]\) stores children of \(p\). DFS or BFS from kill gathers every reachable id. Each process is entered once.

We first construct a graph \(g\) based on \(pid\) and \(ppid\), where \(g[i]\) represents all child processes of process \(i\). Then, starting from the process \(kill\), we perform depth-first search to obtain all killed processes.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the number of processes.

Python3JavaC++GoTypeScriptRust

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 ans

class Solution {
    private Map<Integer, List<Integer>> g = new HashMap<>();
    private List<Integer> ans = new ArrayList<>();

    public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
        int n = pid.size();
        for (int i = 0; i < n; ++i) {
            g.computeIfAbsent(ppid.get(i), k -> new ArrayList<>()).add(pid.get(i));
        }
        dfs(kill);
        return ans;
    }

    private void dfs(int i) {
        ans.add(i);
        for (int j : g.getOrDefault(i, Collections.emptyList())) {
            dfs(j);
        }
    }
}

class Solution {
public:
    vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
        unordered_map<int, vector<int>> g;
        int n = pid.size();
        for (int i = 0; i < n; ++i) {
            g[ppid[i]].push_back(pid[i]);
        }
        vector<int> ans;
        function<void(int)> dfs = [&](int i) {
            ans.push_back(i);
            for (int j : g[i]) {
                dfs(j);
            }
        };
        dfs(kill);
        return ans;
    }
};

func killProcess(pid []int, ppid []int, kill int) (ans []int) {
    g := map[int][]int{}
    for i, p := range ppid {
        g[p] = append(g[p], pid[i])
    }
    var dfs func(int)
    dfs = func(i int) {
        ans = append(ans, i)
        for _, j := range g[i] {
            dfs(j)
        }
    }
    dfs(kill)
    return
}

function killProcess(pid: number[], ppid: number[], kill: number): number[] {
    const g: Map<number, number[]> = new Map();
    for (let i = 0; i < pid.length; ++i) {
        if (!g.has(ppid[i])) {
            g.set(ppid[i], []);
        }
        g.get(ppid[i])?.push(pid[i]);
    }
    const ans: number[] = [];
    const dfs = (i: number) => {
        ans.push(i);
        for (const j of g.get(i) ?? []) {
            dfs(j);
        }
    };
    dfs(kill);
    return ans;
}

use std::collections::HashMap;

impl Solution {
    pub fn kill_process(pid: Vec<i32>, ppid: Vec<i32>, kill: i32) -> Vec<i32> {
        let mut g: HashMap<i32, Vec<i32>> = HashMap::new();
        let mut ans: Vec<i32> = Vec::new();

        let n = pid.len();
        for i in 0..n {
            g.entry(ppid[i]).or_insert(Vec::new()).push(pid[i]);
        }

        Self::dfs(&mut ans, &g, kill);
        ans
    }

    fn dfs(ans: &mut Vec<i32>, g: &HashMap<i32, Vec<i32>>, i: i32) {
        ans.push(i);
        if let Some(children) = g.get(&i) {
            for &j in children {
                Self::dfs(ans, g, j);
            }
        }
    }
}

Solution 2: Explicit Stack

Thinking

Killing a process also kills every descendant. The parent links arrive as two parallel arrays, and \(n\) can be \(5 \times 10^4\), so each process should first store its children. Collecting descendants by recursion along a parent chain uses a call depth equal to the process count and overflows Python once the chain reaches length \(1000\). A stack therefore holds the processes still to visit: a popped process is recorded, and its children are pushed in reverse so the collection order matches a preorder walk of the child lists. The process tree has no cycle, so each process is pushed once.

Build a graph \(g\) from \(pid\) and \(ppid\), where \(g[i]\) is the list of child processes of process \(i\). Start at process \(kill\) and walk with an explicit stack. When process \(i\) is popped, append it to the answer and push its children in reverse order, so the earlier child is popped next. Every descendant is collected once. The problem accepts the ids in any order.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the number of processes.

Python3JavaC++GoTypeScriptRust

class Solution:
    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:
        g = defaultdict(list)
        for i, p in zip(pid, ppid):
            g[p].append(i)
        ans = []
        stk = [kill]
        while stk:
            i = stk.pop()
            ans.append(i)
            for j in reversed(g[i]):
                stk.append(j)
        return ans

class Solution {
    public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
        Map<Integer, List<Integer>> g = new HashMap<>();
        int n = pid.size();
        for (int i = 0; i < n; ++i) {
            g.computeIfAbsent(ppid.get(i), k -> new ArrayList<>()).add(pid.get(i));
        }
        List<Integer> ans = new ArrayList<>();
        Deque<Integer> stk = new ArrayDeque<>();
        stk.push(kill);
        while (!stk.isEmpty()) {
            int i = stk.pop();
            ans.add(i);
            List<Integer> children = g.getOrDefault(i, List.of());
            for (int k = children.size() - 1; k >= 0; --k) {
                stk.push(children.get(k));
            }
        }
        return ans;
    }
}

class Solution {
public:
    vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
        unordered_map<int, vector<int>> g;
        int n = pid.size();
        for (int i = 0; i < n; ++i) {
            g[ppid[i]].push_back(pid[i]);
        }
        vector<int> ans;
        vector<int> stk = {kill};
        while (!stk.empty()) {
            int i = stk.back();
            stk.pop_back();
            ans.push_back(i);
            auto it = g.find(i);
            if (it == g.end()) {
                continue;
            }
            auto& children = it->second;
            for (int k = (int) children.size() - 1; k >= 0; --k) {
                stk.push_back(children[k]);
            }
        }
        return ans;
    }
};

func killProcess(pid []int, ppid []int, kill int) (ans []int) {
    g := map[int][]int{}
    for i, p := range ppid {
        g[p] = append(g[p], pid[i])
    }
    stk := []int{kill}
    for len(stk) > 0 {
        i := stk[len(stk)-1]
        stk = stk[:len(stk)-1]
        ans = append(ans, i)
        children := g[i]
        for k := len(children) - 1; k >= 0; k-- {
            stk = append(stk, children[k])
        }
    }
    return
}

function killProcess(pid: number[], ppid: number[], kill: number): number[] {
    const g: Map<number, number[]> = new Map();
    for (let i = 0; i < pid.length; ++i) {
        if (!g.has(ppid[i])) {
            g.set(ppid[i], []);
        }
        g.get(ppid[i])!.push(pid[i]);
    }
    const ans: number[] = [];
    const stk: number[] = [kill];
    while (stk.length) {
        const i = stk.pop()!;
        ans.push(i);
        const children = g.get(i) ?? [];
        for (let k = children.length - 1; k >= 0; --k) {
            stk.push(children[k]);
        }
    }
    return ans;
}

use std::collections::HashMap;

impl Solution {
    pub fn kill_process(pid: Vec<i32>, ppid: Vec<i32>, kill: i32) -> Vec<i32> {
        let mut g: HashMap<i32, Vec<i32>> = HashMap::new();
        let n = pid.len();
        for i in 0..n {
            g.entry(ppid[i]).or_insert(Vec::new()).push(pid[i]);
        }
        let mut ans = Vec::new();
        let mut stk = vec![kill];
        while let Some(i) = stk.pop() {
            ans.push(i);
            if let Some(children) = g.get(&i) {
                for &j in children.iter().rev() {
                    stk.push(j);
                }
            }
        }
        ans
    }
}

582. Kill Process 🔒

Description

Solutions

Solution 1: DFS

Solution 2: Explicit Stack

Comments