Problem

You are maintaining a project that has n methods numbered from 0 to n -1.

You are given two integers n and k, and a 2D integer array invocations, where invocations[i] = [ai, bi] indicates that method ai invokes method bi.

There is a known bug in method k. Method k, along with any method invoked by it, either directly or indirectly , are considered suspicious and we aim to remove them.

A group of methods can only be removed if no method outside the group invokes any methods within it.

Return an array containing all the remaining methods after removing all the suspicious methods. You may return the answer in any order. If it is not possible to remove all the suspicious methods, none should be removed.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


Input: n = 4, k = 1, invocations = [[1,2],[0,1],[3,2]]

Output: [0,1,2,3]

Explanation:

![](https://assets.leetcode.com/uploads/2024/07/18/graph-2.png)

Method 2 and method 1 are suspicious, but they are directly invoked by methods
3 and 0, which are not suspicious. We return all elements without removing
anything.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


Input: n = 5, k = 0, invocations = [[1,2],[0,2],[0,1],[3,4]]

Output: [3,4]

Explanation:

![](https://assets.leetcode.com/uploads/2024/07/18/graph-3.png)

Methods 0, 1, and 2 are suspicious and they are not directly invoked by any
other method. We can remove them.

Example 3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


Input: n = 3, k = 2, invocations = [[1,2],[0,1],[2,0]]

Output: []

Explanation:

![](https://assets.leetcode.com/uploads/2024/07/20/graph.png)

All methods are suspicious. We can remove them.

Constraints

  • 1 <= n <= 10^5
  • 0 <= k <= n - 1
  • 0 <= invocations.length <= 2 * 10^5
  • invocations[i] == [ai, bi]
  • 0 <= ai, bi <= n - 1
  • ai != bi
  • invocations[i] != invocations[j]

Solution

Method 1 - BFS/DFS for Suspicious Group and In-Degree Check

Intuition

We need to find all methods reachable from k (the suspicious group). We can only remove them if no method outside the group invokes any method inside. Use BFS/DFS to find the group, then check all invocations for incoming edges from outside.

Approach

  1. Build a graph of invocations (adjacency list) and a reverse graph (for in-degree check).
  2. Use BFS/DFS from k to find all suspicious methods.
  3. For each invocation [ai, bi], if ai is not suspicious and bi is, removal is impossible.
  4. If possible, return all non-suspicious methods; else, return all methods.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;

vector<int> removeMethods(int n, int k, vector<vector<int>>& invocations) {
    vector<vector<int>> g(n);
    for (auto& e : invocations) g[e[0]].push_back(e[1]);
    vector<bool> suspicious(n, false);
    queue<int> q;
    q.push(k);
    suspicious[k] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u]) {
            if (!suspicious[v]) {
                suspicious[v] = true;
                q.push(v);
            }
        }
    }
    for (auto& e : invocations) {
        if (!suspicious[e[0]] && suspicious[e[1]]) return vector<int>(n); // return all
    }
    vector<int> res;
    for (int i = 0; i < n; ++i) if (!suspicious[i]) res.push_back(i);
    return res;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

func removeMethods(n, k int, invocations [][]int) []int {
    g := make([][]int, n)
    for _, e := range invocations {
        g[e[0]] = append(g[e[0]], e[1])
    }
    suspicious := make([]bool, n)
    q := []int{k}
    suspicious[k] = true
    for len(q) > 0 {
        u := q[0]; q = q[1:]
        for _, v := range g[u] {
            if !suspicious[v] {
                suspicious[v] = true
                q = append(q, v)
            }
        }
    }
    for _, e := range invocations {
        if !suspicious[e[0]] && suspicious[e[1]] {
            res := make([]int, n)
            for i := 0; i < n; i++ { res[i] = i }
            return res
        }
    }
    res := []int{}
    for i := 0; i < n; i++ {
        if !suspicious[i] { res = append(res, i) }
    }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

import java.util.*;
public class Solution {
    public List<Integer> removeMethods(int n, int k, int[][] invocations) {
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        for (int[] e : invocations) g.get(e[0]).add(e[1]);
        boolean[] suspicious = new boolean[n];
        Queue<Integer> q = new LinkedList<>();
        q.add(k);
        suspicious[k] = true;
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : g.get(u)) {
                if (!suspicious[v]) {
                    suspicious[v] = true;
                    q.add(v);
                }
            }
        }
        for (int[] e : invocations) {
            if (!suspicious[e[0]] && suspicious[e[1]]) {
                List<Integer> all = new ArrayList<>();
                for (int i = 0; i < n; i++) all.add(i);
                return all;
            }
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < n; i++) if (!suspicious[i]) res.add(i);
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

fun removeMethods(n: Int, k: Int, invocations: Array<IntArray>): List<Int> {
    val g = Array(n) { mutableListOf<Int>() }
    for (e in invocations) g[e[0]].add(e[1])
    val suspicious = BooleanArray(n)
    val q = ArrayDeque<Int>()
    q.add(k)
    suspicious[k] = true
    while (q.isNotEmpty()) {
        val u = q.removeFirst()
        for (v in g[u]) {
            if (!suspicious[v]) {
                suspicious[v] = true
                q.add(v)
            }
        }
    }
    for (e in invocations) {
        if (!suspicious[e[0]] && suspicious[e[1]]) return (0 until n).toList()
    }
    return (0 until n).filter { !suspicious[it] }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def removeMethods(n, k, invocations):
    from collections import deque
    g = [[] for _ in range(n)]
    for a, b in invocations:
        g[a].append(b)
    suspicious = [False] * n
    q = deque([k])
    suspicious[k] = True
    while q:
        u = q.popleft()
        for v in g[u]:
            if not suspicious[v]:
                suspicious[v] = True
                q.append(v)
    for a, b in invocations:
        if not suspicious[a] and suspicious[b]:
            return list(range(n))
    return [i for i in range(n) if not suspicious[i]]
1

// Omitted for brevity, same logic as above using Vec and VecDeque

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

function removeMethods(n: number, k: number, invocations: number[][]): number[] {
    const g: number[][] = Array.from({length: n}, () => []);
    for (const [a, b] of invocations) g[a].push(b);
    const suspicious = Array(n).fill(false);
    const q: number[] = [k];
    suspicious[k] = true;
    while (q.length) {
        const u = q.shift()!;
        for (const v of g[u]) {
            if (!suspicious[v]) {
                suspicious[v] = true;
                q.push(v);
            }
        }
    }
    for (const [a, b] of invocations) {
        if (!suspicious[a] && suspicious[b]) return Array.from({length: n}, (_, i) => i);
    }
    return Array.from({length: n}, (_, i) => i).filter(i => !suspicious[i]);
}

Complexity

  • ⏰ Time complexity: O(N + M), where N = n and M = len(invocations).
  • 🧺 Space complexity: O(N + M).