Remove Methods From Project
MedPrompt
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:
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:
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:
All methods are suspicious. We can remove them.
Constraints:
1 <= n <= 1050 <= k <= n - 10 <= invocations.length <= 2 * 105invocations[i] == [ai, bi]0 <= ai, bi <= n - 1ai != biinvocations[i] != invocations[j]
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize a
SetcalledsuspiciousMethodsand add the initial buggy methodk. - Enter a loop that continues as long as new methods are being added to the
suspiciousMethodsset. In each iteration, scan the entireinvocationsarray. - For each invocation
[caller, callee], ifcalleris insuspiciousMethodsandcalleeis not, addcalleeto the set. - Continue this process until no new methods are added in a full pass.
- Once the
suspiciousMethodsset is finalized, check the removal condition by iterating throughinvocationsone more time. - If a non-suspicious method calls a suspicious one, the condition is violated. Return all methods from
0ton-1. - If the condition is met, create a list of remaining methods by including only those not present in
suspiciousMethods.
Walkthrough
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
0ton-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.
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(); }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Build an adjacency list representation of the graph from the
invocationsarray, whereadj[u]stores methods called byu. - Perform a Breadth-First Search (BFS) starting from method
kto find all reachable methods. Mark these as suspicious using a boolean array. - Iterate through all
invocations[u, v]. Ifvis suspicious anduis not, the removal condition is violated. - If the condition is violated, return all
nmethods. - Otherwise, return all methods that were not marked as suspicious.
Walkthrough
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
0ton-1. - If the condition is met after checking all invocations, we construct and return a list of all methods
iwhereisSuspicious[i]isfalse.
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(); }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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); } } }}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; }};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]]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.