# Remove Methods From Project
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/remove-methods-from-project)
Canonical: https://scaleengineer.com/dsa/problems/remove-methods-from-project
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Graph
---
## 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.

**Example 1:**

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

**Output:** \[0,1,2,3\]

**Explanation:**

![](https://assets.glich.co/dsa/remove-methods-from-project/image0.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:**

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

**Output:** \[3,4\]

**Explanation:**

![](https://assets.glich.co/dsa/remove-methods-from-project/image1.png)

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

**Example 3:**

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

**Output:** \[\]

**Explanation:**

![](https://assets.glich.co/dsa/remove-methods-from-project/image2.png)

All methods are suspicious. We can remove them.

**Constraints:**

* `1 <= n <= 105`
* `0 <= k <= n - 1`
* `0 <= invocations.length <= 2 * 105`
* `invocations[i] == [ai, bi]`
* `0 <= ai, bi <= n - 1`
* `ai != bi`
* `invocations[i] != invocations[j]`

# Approaches
## Iterative Expansion without Adjacency List
This approach avoids building an explicit graph structure like an adjacency list. Instead, it iteratively finds all suspicious methods by repeatedly scanning the `invocations` list until no more suspicious methods can be found.
**Time:** O(N * E), where N is the number of methods and E is the number of invocations. In the worst case (a long chain of invocations), the `while` loop can run up to N times, and each iteration scans all E invocations. · **Space:** O(N), where N is the number of methods. This space is used to store the `suspiciousMethods` set.
**Pros:** Conceptually simple, as it does not require building an explicit graph data structure.
**Cons:** Highly inefficient due to the `O(N * E)` time complexity, which will likely cause a 'Time Limit Exceeded' error on larger test cases.
### Explanation
This approach works by first identifying all suspicious methods and then checking if they can be removed as a group.

**1. Identifying Suspicious Methods:**
We start with a set containing only the initial buggy method, `k`. We then repeatedly scan the entire `invocations` list. If we find an invocation `[u, v]` where method `u` is already in our suspicious set but `v` is not, we add `v` to the set. This process continues until a full scan of `invocations` results in no new methods being added to the suspicious set. This ensures we have found all methods reachable from `k`.

**2. Checking the Removal Condition:**
Once the set of suspicious methods is complete, we iterate through the `invocations` list again. For each invocation `[u, v]`, we check if a non-suspicious method `u` calls a suspicious method `v`. If we find even one such case, the rule is violated, and no methods can be removed.

**3. Generating the Output:**
*   If the removal condition is violated, we return an array of all methods from `0` to `n-1`.
*   If the condition holds, we return a new array containing only the methods that are not in our suspicious set.

This method is slow because finding all suspicious methods can require many passes over the entire `invocations` list.

```java
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

class Solution {
    public int[] removeMethods(int n, int k, int[][] invocations) {
        Set<Integer> suspiciousMethods = new HashSet<>();
        suspiciousMethods.add(k);

        boolean newSuspiciousFound = true;
        while (newSuspiciousFound) {
            newSuspiciousFound = false;
            for (int[] invocation : invocations) {
                int caller = invocation[0];
                int callee = invocation[1];
                if (suspiciousMethods.contains(caller) && !suspiciousMethods.contains(callee)) {
                    suspiciousMethods.add(callee);
                    newSuspiciousFound = true;
                }
            }
        }

        for (int[] invocation : invocations) {
            int caller = invocation[0];
            int callee = invocation[1];
            if (suspiciousMethods.contains(callee) && !suspiciousMethods.contains(caller)) {
                // Condition violated, return all methods
                return IntStream.range(0, n).toArray();
            }
        }

        // Condition met, return non-suspicious methods
        List<Integer> remainingMethods = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (!suspiciousMethods.contains(i)) {
                remainingMethods.add(i);
            }
        }
        return remainingMethods.stream().mapToInt(i -> i).toArray();
    }
}
```
### Algorithm
*   Initialize a `Set` called `suspiciousMethods` and add the initial buggy method `k`.
*   Enter a loop that continues as long as new methods are being added to the `suspiciousMethods` set. In each iteration, scan the entire `invocations` array.
*   For each invocation `[caller, callee]`, if `caller` is in `suspiciousMethods` and `callee` is not, add `callee` to the set.
*   Continue this process until no new methods are added in a full pass.
*   Once the `suspiciousMethods` set is finalized, check the removal condition by iterating through `invocations` one more time.
*   If a non-suspicious method calls a suspicious one, the condition is violated. Return all methods from `0` to `n-1`.
*   If the condition is met, create a list of remaining methods by including only those not present in `suspiciousMethods`.

## Optimal Graph Traversal (BFS)
This is the standard and efficient approach for this type of problem. We model the methods and their invocations as a directed graph. Then, we use a graph traversal algorithm like Breadth-First Search (BFS) to solve the problem.
**Time:** O(N + E), where N is the number of methods and E is the number of invocations. Building the graph, running BFS, and checking the condition are all linear in the size of the graph. · **Space:** O(N + E), where N is the number of methods and E is the number of invocations. This space is required for the adjacency list, the `isSuspicious` array, and the BFS queue.
**Pros:** Highly efficient with an optimal time complexity, making it suitable for large datasets.; Follows a standard and robust pattern for graph reachability problems.
**Cons:** Requires more space to store the adjacency list compared to the iterative approach, but this is a necessary trade-off for time efficiency.
### Explanation
This optimal solution treats the problem as a graph problem, which allows for a much more efficient solution.

**1. Graph Representation:**
First, we model the methods and invocations as a directed graph. The methods are the vertices (nodes), and an invocation `[u, v]` is a directed edge from `u` to `v`. We build an adjacency list for this graph, where `adj[u]` contains all methods directly called by `u`.

**2. Finding Suspicious Methods (BFS):**
With the graph built, finding all suspicious methods is equivalent to finding all nodes reachable from node `k`. A Breadth-First Search (BFS) is perfect for this. We start a BFS from `k`, using a queue and a `isSuspicious` boolean array to keep track of visited nodes. All nodes visited during the BFS are marked as suspicious.

**3. Checking the Removal Condition:**
After the BFS, we have a complete list of suspicious methods. We then iterate through the original `invocations` list `[u, v]`. If we find an edge where the caller `u` is not suspicious (`!isSuspicious[u]`) but the callee `v` is (`isSuspicious[v]`), it means an external method calls into the suspicious group. This violates the removal condition.

**4. Generating the Output:**
*   If the condition is violated, we return all methods from `0` to `n-1`.
*   If the condition is met after checking all invocations, we construct and return a list of all methods `i` where `isSuspicious[i]` is `false`.

```java
import java.util.*;
import java.util.stream.IntStream;

class Solution {
    public int[] removeMethods(int n, int k, int[][] invocations) {
        // Step 1: Build the graph (adjacency list)
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] invocation : invocations) {
            adj.get(invocation[0]).add(invocation[1]);
        }

        // Step 2: Identify suspicious methods using BFS
        boolean[] isSuspicious = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();

        isSuspicious[k] = true;
        queue.add(k);

        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : adj.get(u)) {
                if (!isSuspicious[v]) {
                    isSuspicious[v] = true;
                    queue.add(v);
                }
            }
        }

        // Step 3: Check the removal condition
        for (int[] invocation : invocations) {
            int caller = invocation[0];
            int callee = invocation[1];
            if (isSuspicious[callee] && !isSuspicious[caller]) {
                // A non-suspicious method invokes a suspicious one.
                // Removal is not possible. Return all methods.
                return IntStream.range(0, n).toArray();
            }
        }

        // Step 4: Removal is possible. Collect and return remaining methods.
        List<Integer> remainingMethods = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (!isSuspicious[i]) {
                remainingMethods.add(i);
            }
        }
        return remainingMethods.stream().mapToInt(i -> i).toArray();
    }
}
```
### Algorithm
*   Build an adjacency list representation of the graph from the `invocations` array, where `adj[u]` stores methods called by `u`.
*   Perform a Breadth-First Search (BFS) starting from method `k` to find all reachable methods. Mark these as suspicious using a boolean array.
*   Iterate through all `invocations` `[u, v]`. If `v` is suspicious and `u` is not, the removal condition is violated.
*   If the condition is violated, return all `n` methods.
*   Otherwise, return all methods that were not marked as suspicious.

# Solutions
### Java

```java
class Solution {
private
  boolean[] suspicious;
private
  boolean[] vis;
private
  List<Integer>[] f;
private
  List<Integer>[] g;
public
  List<Integer> remainingMethods(int n, int k, int[][] invocations) {
    suspicious = new boolean[n];
    vis = new boolean[n];
    f = new List[n];
    g = new List[n];
    Arrays.setAll(f, i->new ArrayList<>());
    Arrays.setAll(g, i->new ArrayList<>());
    for (var e : invocations) {
      int a = e[0], b = e[1];
      f[a].add(b);
      f[b].add(a);
      g[a].add(b);
    }
    dfs(k);
    for (int i = 0; i < n; ++i) {
      if (!suspicious[i] && !vis[i]) {
        dfs2(i);
      }
    }
    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < n; ++i) {
      if (!suspicious[i]) {
        ans.add(i);
      }
    }
    return ans;
  }
private
  void dfs(int i) {
    suspicious[i] = true;
    for (int j : g[i]) {
      if (!suspicious[j]) {
        dfs(j);
      }
    }
  }
private
  void dfs2(int i) {
    vis[i] = true;
    for (int j : f[i]) {
      if (!vis[j]) {
        suspicious[j] = false;
        dfs2(j);
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> remainingMethods(int n, int k, vector<vector<int>> &invocations) {
    vector<bool> suspicious(n);
    vector<bool> vis(n);
    vector<int> f[n];
    vector<int> g[n];
    for (const auto &e : invocations) {
      int a = e[0], b = e[1];
      f[a].push_back(b);
      f[b].push_back(a);
      g[a].push_back(b);
    }
    auto dfs = [&](auto &&dfs, int i) -> void {
      suspicious[i] = true;
      for (int j : g[i]) {
        if (!suspicious[j]) {
          dfs(dfs, j);
        }
      }
    };
    dfs(dfs, k);
    auto dfs2 = [&](auto &&dfs2, int i) -> void {
      vis[i] = true;
      for (int j : f[i]) {
        if (!vis[j]) {
          suspicious[j] = false;
          dfs2(dfs2, j);
        }
      }
    };
    for (int i = 0; i < n; ++i) {
      if (!suspicious[i] && !vis[i]) {
        dfs2(dfs2, i);
      }
    }
    vector<int> ans;
    for (int i = 0; i < n; ++i) {
      if (!suspicious[i]) {
        ans.push_back(i);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def remainingMethods(self, n: int, k: int, invocations: List[List[int]]) -> List[int]: def dfs(i: int): suspicious[i] = True for j in g[i]: if not suspicious[j]: dfs(j) def dfs2(i: int): vis[i] = True for j in f[i]: if not vis[j]: suspicious[j] = False dfs2(j) f = [[] for _ in range(n)] g = [[] for _ in range(n)] for a, b in invocations: f[a]. append(b) f[b]. append(a) g[a]. append(b) suspicious = [False] * n dfs(k) vis = [False] * n ans = [] for i in range(n): if not suspicious[i] and not vis[i]: dfs2(i) return [i for i in range(n) if not suspicious[i]]

```