Remove Methods From Project — Solution in Python, Java & C++
Remove Methods From Project solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Remove Methods From Project is a medium coding problem on depth-first search, breadth-first search and graph, asked in Amazon interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Breadth-First Search, Graph
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A project has n methods numbered 0 to n - 1. Each invocations[i] = [ai, bi] means method ai calls method bi.
Method k has a known bug. It is suspicious, and so is every method it calls directly or indirectly.
You want to delete all suspicious methods together, but only if no method outside that group calls into it. If some non-suspicious method calls a suspicious one, nothing can be removed.
Return the methods that remain after deleting as much as the rule allows, sorted in increasing order.
Example 1
Input: n = 4, k = 1, invocations = [[1,2],[0,1],[3,2]]
Output: [0,1,2,3]
Explanation: Methods 1 and 2 are suspicious, but method 0 calls 1 (and method 3 calls 2), so nothing is removed.
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 only call each other, so they are removed.
Example 3
Input: n = 3, k = 2, invocations = [[1,2],[0,1],[2,0]]
Output: []
Explanation: Every method is reachable from 2, so all of them are removed.
Constraints
1 <= n <= 10^50 <= k <= n - 10 <= invocations.length <= 2 * 10^5invocations[i] == [ai, bi]0 <= ai, bi <= n - 1ai != biinvocations[i] != invocations[j] for i != j
Hints for Remove Methods From Project
Hint 1
First find the suspicious group: every method reachable from
kalong the call edges.Hint 2
A BFS or DFS from
kover the directed edges marks the group in O(n + m).Hint 3
Then scan every call
a → b: ifais outside the group andbinside it, nothing can be removed. Otherwise return the methods outside the group.
How to solve Remove Methods From Project
The decision is all-or-nothing, so compute the suspicious set by reachability and then check a single condition: does any edge enter the set from outside?
Approach
- Build the directed adjacency lists of the calls.
- BFS from
k, marking every method reached as suspicious. - For each call
[a, b], ifais not suspicious butbis, return every method0 … n - 1. - Otherwise return the non-suspicious methods in increasing order.
Why it works
The suspicious set is closed under calls by construction (anything a suspicious method calls is suspicious), so deleting it never breaks a call that starts inside it. The only calls that could break start outside the set and end inside, and those are exactly the ones the scan looks for.
Complexity
- Time —
O(n + m) - Space —
O(n + m)
Pitfalls
- Edges are directed: a method calling
kis not suspicious, it is what blocks the removal. - If removal is blocked the answer is all methods, including the suspicious ones.
- An empty answer is valid — when every method is suspicious.
Reference solution
Python
from typing import List
def remainingMethods(n: int, k: int, invocations: List[List[int]]) -> List[int]:
adj = [[] for _ in range(n)]
for a, b in invocations:
adj[a].append(b)
sus = [False] * n
sus[k] = True
stack = [k]
while stack:
u = stack.pop()
for v in adj[u]:
if not sus[v]:
sus[v] = True
stack.append(v)
for a, b in invocations:
if not sus[a] and sus[b]:
return list(range(n))
return [i for i in range(n) if not sus[i]]Java
public static int[] remainingMethods(int n, int k, int[][] invocations) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : invocations) adj.get(e[0]).add(e[1]);
boolean[] sus = new boolean[n];
sus[k] = true;
int[] stack = new int[n];
int top = 0;
stack[top++] = k;
while (top > 0) {
int u = stack[--top];
for (int v : adj.get(u)) if (!sus[v]) { sus[v] = true; stack[top++] = v; }
}
boolean blocked = false;
for (int[] e : invocations) if (!sus[e[0]] && sus[e[1]]) { blocked = true; break; }
int cnt = 0;
for (int i = 0; i < n; i++) if (blocked || !sus[i]) cnt++;
int[] out = new int[cnt];
int w = 0;
for (int i = 0; i < n; i++) if (blocked || !sus[i]) out[w++] = i;
return out;
}C++
vector<int> remainingMethods(int n, int k, vector<vector<int>>& invocations) {
vector<vector<int>> adj(n);
for (auto& e : invocations) adj[e[0]].push_back(e[1]);
vector<bool> sus(n, false);
sus[k] = true;
vector<int> stack = {k};
while (!stack.empty()) {
int u = stack.back();
stack.pop_back();
for (int v : adj[u]) if (!sus[v]) { sus[v] = true; stack.push_back(v); }
}
bool blocked = false;
for (auto& e : invocations) if (!sus[e[0]] && sus[e[1]]) { blocked = true; break; }
vector<int> out;
for (int i = 0; i < n; i++) if (blocked || !sus[i]) out.push_back(i);
return out;
}JavaScript
var remainingMethods = function(n, k, invocations) {
var adj = [], sus = [];
for (var i = 0; i < n; i++) { adj.push([]); sus.push(false); }
for (var e = 0; e < invocations.length; e++) adj[invocations[e][0]].push(invocations[e][1]);
sus[k] = true;
var stack = [k];
while (stack.length > 0) {
var u = stack.pop();
for (var j = 0; j < adj[u].length; j++) {
var v = adj[u][j];
if (!sus[v]) { sus[v] = true; stack.push(v); }
}
}
var blocked = false;
for (var t = 0; t < invocations.length; t++) {
if (!sus[invocations[t][0]] && sus[invocations[t][1]]) { blocked = true; break; }
}
var out = [];
for (var x = 0; x < n; x++) if (blocked || !sus[x]) out.push(x);
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)