Remove Methods From Project solution and explanation
6 more videos on this problem
Leetcode | Weekly Contest 418 | 3312. Sorted GCD Pair Queries | 3310. Remove Methods From ProjectPretest Passed · 34:36 · 1K views
Leetcode Weekly Contest 418 | 3310. Remove Methods From Project | DFS | CodeFodCodeFod · 17:24 · 659 views
3310. Remove Methods From Project (Leetcode Medium)Programming Live with Larry · 12:00 · 427 views
LeetCode 3310: Remove Methods From Project | Weekly Contest 418 | Graph DFS C++ SolutionDebugAndDeploy · 11:56 · 164 views
Leetcode 3310 | Remove Methods From Project | Weekly Contest 418Road To FAANG · 9:41 · 142 views
3310. Remove Methods From Project || Leetcode Medium || Weekly Contest 418 LolCode · 7:55 · 103 views
Leetcode 3310 Remove Methods From Project - In Hindi ExplanationAlgorithmicIQ · 20:14 · 26 views
The 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:
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]
Approach overview
Problem Overview: You’re given a project with n methods and a list of method calls forming a directed graph. Starting from a suspicious method, determine which methods can be removed. A method should be removed if it is reachable from the suspicious method and no remaining method depends on it.
Approach 1: Graph Reachability Using DFS (O(n + m) time, O(n + m) space)
Model the project as a directed graph where each node represents a method and each edge u → v means method u calls method v. Start a depth-first search from the suspicious method and mark every reachable node. These nodes represent methods potentially removable because they are part of the suspicious dependency chain. After computing this reachable set, scan all edges again to check whether any method outside the set calls a method inside it. If such an incoming edge exists, the removal would break a valid dependency, so no methods should be deleted. Otherwise, every reachable node can be safely removed and the remaining nodes form the final answer. DFS works well here because it naturally explores dependency chains and keeps the implementation compact using recursion or a stack.
Approach 2: Graph Reachability Using BFS (O(n + m) time, O(n + m) space)
This approach performs the same reachability check but uses a queue instead of recursion. Build the adjacency list and start a breadth-first traversal from the suspicious method. Push the starting node into a queue, repeatedly pop a method, and enqueue all unvisited neighbors it calls. Every visited node becomes part of the removable set. Once traversal finishes, iterate over all edges to verify that no method outside the set points to one inside it. If such an edge exists, removal is invalid; otherwise return all methods not marked as reachable. BFS is often preferred when recursion depth might become large or when you want explicit control over traversal order.
Both solutions rely on classic graph traversal patterns used in Depth-First Search and Breadth-First Search. The key insight is recognizing that method dependencies form a directed graph, and the suspicious method defines a reachability region that determines which methods are candidates for removal.
Recommended for interviews: Either DFS or BFS is acceptable since both run in O(n + m). Interviewers mainly expect you to recognize the problem as a graph reachability check and then validate that no external node depends on the removable set. Starting with DFS usually demonstrates strong understanding of graph traversal, while BFS provides the same optimal complexity with an iterative approach.
Approach 1: Graph Reachability Using DFS
Model the problem as a graph where each method is a node and each invocation is a directed edge between nodes. Use a Depth First Search (DFS) to find all the methods that can be reached starting from the method with the bug, k. Mark these methods as suspicious. After marking, check if any edges exist from non-suspicious nodes to suspicious nodes. If such an edge exists, deletion isn't possible. If no such edges exist, return the non-suspicious methods.
def remove_suspicious_methods(n, k, invocations):
from collections import defaultdict
graph = defaultdict(list)
reverse_graph = defaultdict(list)
for a, b in invocations:
graph[a].append(b)
reverse_graph[b].append(a)
suspicious = set()
def dfs(node):
if node in suspicious:
return
suspicious.add(node)
for neighbor in graph[node]:
dfs(neighbor)
dfs(k)
for node in suspicious:
if any(invoker not in suspicious for invoker in reverse_graph[node]):
return list(range(n))
return [i for i in range(n) if i not in suspicious]function removeSuspiciousMethods(n, k, invocations) {
const graph = Array.from({ length: n }, () => []);
const reverseGraph = Array.from({ length: n }, () => []);
for (let [a, b] of invocations) {
graph[a].push(b);
reverseGraph[b].push(a);
}
const suspicious = new Set();
const dfs = (node) => {
if (suspicious.has(node)) return;
suspicious.add(node);
for (let neighbor of graph[node]) {
dfs(neighbor);
}
};
dfs(k);
for (let node of suspicious) {
if (reverseGraph[node].some(invoker => !suspicious.has(invoker))) {
return [...Array(n).keys()];
}
}
return [...Array(n).keys()].filter(i => !suspicious.has(i));
}This solution creates a graph and a reverse graph to track invocations. It defines a DFS function that collects all suspicious nodes starting from k. After identifying all suspicious nodes, it checks if any invocations point to a suspicious node from a non-suspicious one using the reverse graph. If such an edge exists, no methods can be removed. Otherwise, it returns all non-suspicious methods.
Time Complexity: O(n + m), where n is the number of methods and m is the number of invocations. Space Complexity: O(n + m) for the graph representation.
Approach 2: Graph Reachability Using BFS
This approach uses Breadth First Search (BFS) instead of DFS to identify all suspicious methods invoked by method k, directly or indirectly. With BFS, iterate level by level to mark all suspicious methods starting from node k. After marking, check if any suspicious method is invoked by a non-suspicious method.
#include <vector>
#include <queue>
using namespace std;
vector<int> removeSuspiciousMethods(int n, int k, vector<pair<int, int>>& invocations) {
vector<vector<int>> graph(n), reverseGraph(n);
for (auto& [a, b] : invocations) {
graph[a].push_back(b);
reverseGraph[b].push_back(a);
}
vector<bool> suspicious(n, false);
queue<int> q;
q.push(k);
suspicious[k] = true;
while (!q.empty()) {
int node = q.front();
q.pop();
for (int neighbor : graph[node]) {
if (!suspicious[neighbor]) {
suspicious[neighbor] = true;
q.push(neighbor);
}
}
}
for (int node = 0; node < n; ++node) {
if (suspicious[node]) {
for (int invoker : reverseGraph[node]) {
if (!suspicious[invoker]) {
return vector<int>(n);
}
}
}
}
vector<int> result;
for (int i = 0; i < n; ++i) {
if (!suspicious[i]) {
result.push_back(i);
}
}
return result;
}#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
typedef struct {
int *data;
int size;
int capacity;
} Vector;
void init(Vector *vec) {
vec->data = malloc(sizeof(int) * 10);
vec->size = 0;
vec->capacity = 10;
}
void push_back(Vector *vec, int val) {
if (vec->size == vec->capacity) {
vec->capacity *= 2;
vec->data = realloc(vec->data, sizeof(int) * vec->capacity);
}
vec->data[vec->size++] = val;
}
void vector_free(Vector *vec) {
free(vec->data);
}
int* remove_suspicious_methods(int n, int k, int** invocations, int invocationsSize, int* invocationsColSize, int* returnSize) {
Vector *graph = malloc(sizeof(Vector) * n);
Vector *reverseGraph = malloc(sizeof(Vector) * n);
for (int i = 0; i < n; ++i) {
init(&graph[i]);
init(&reverseGraph[i]);
}
for (int i = 0; i < invocationsSize; ++i) {
int a = invocations[i][0], b = invocations[i][1];
push_back(&graph[a], b);
push_back(&reverseGraph[b], a);
}
bool *suspicious = calloc(n, sizeof(bool));
Vector queue;
init(&queue);
push_back(&queue, k);
suspicious[k] = true;
for (int i = 0; i < queue.size; ++i) {
int node = queue.data[i];
for (int j = 0; j < graph[node].size; ++j) {
int neighbor = graph[node].data[j];
if (!suspicious[neighbor]) {
suspicious[neighbor] = true;
push_back(&queue, neighbor);
}
}
}
for (int i = 0; i < n; ++i) {
if (suspicious[i]) {
for (int j = 0; j < reverseGraph[i].size; ++j) {
int invoker = reverseGraph[i].data[j];
if (!suspicious[invoker]) {
*returnSize = n;
vector_free(&queue);
for (int i = 0; i < n; ++i) {
vector_free(&graph[i]);
vector_free(&reverseGraph[i]);
}
return NULL;
}
}
}
}
int *result = malloc(sizeof(int) * n);
*returnSize = 0;
for (int i = 0; i < n; ++i) {
if (!suspicious[i]) {
result[(*returnSize)++] = i;
}
}
free(suspicious);
vector_free(&queue);
for (int i = 0; i < n; ++i) {
vector_free(&graph[i]);
vector_free(&reverseGraph[i]);
}
free(graph);
free(reverseGraph);
return result;
}In this C++ solution, BFS is used to traverse the graph starting from node k, marking all reachable nodes as suspicious. It then checks reverse edges to guarantee no non-suspicious node links to a suspicious node before returning the list of non-suspicious nodes.
Time Complexity: O(n + m), due to graph traversal with BFS. Space Complexity: O(n + m), used for storing adjacency lists and BFS queue.
Approach 3: Two DFS
We can start from k and find all suspicious methods, recording them in the array suspicious. Then, we traverse from 0 to n-1, starting from all non-suspicious methods, and mark all reachable methods as non-suspicious. Finally, we return all non-suspicious methods.
The time complexity is O(n + m), and the space complexity is O(n + m). Here, n and m represent the number of methods and the number of call relationships, respectively.
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);
}
}
}
}function remainingMethods(n: number, k: number, invocations: number[][]): number[] {
const suspicious: boolean[] = Array(n).fill(false);
const vis: boolean[] = Array(n).fill(false);
const f: number[][] = Array.from({ length: n }, () => []);
const g: number[][] = Array.from({ length: n }, () => []);
for (const [a, b] of invocations) {
f[a].push(b);
f[b].push(a);
g[a].push(b);
}
const dfs = (i: number) => {
suspicious[i] = true;
for (const j of g[i]) {
if (!suspicious[j]) {
dfs(j);
}
}
};
dfs(k);
const dfs2 = (i: number) => {
vis[i] = true;
for (const j of f[i]) {
if (!vis[j]) {
suspicious[j] = false;
dfs2(j);
}
}
};
for (let i = 0; i < n; i++) {
if (!suspicious[i] && !vis[i]) {
dfs2(i);
}
}
return Array.from({ length: n }, (_, i) => i).filter(i => !suspicious[i]);
}func remainingMethods(n int, k int, invocations [][]int) []int {
suspicious := make([]bool, n)
vis := make([]bool, n)
f := make([][]int, n)
g := make([][]int, n)
for _, e := range invocations {
a, b := e[0], e[1]
f[a] = append(f[a], b)
f[b] = append(f[b], a)
g[a] = append(g[a], b)
}
var dfs func(int)
dfs = func(i int) {
suspicious[i] = true
for _, j := range g[i] {
if !suspicious[j] {
dfs(j)
}
}
}
dfs(k)
var dfs2 func(int)
dfs2 = func(i int) {
vis[i] = true
for _, j := range f[i] {
if !vis[j] {
suspicious[j] = false
dfs2(j)
}
}
}
for i := 0; i < n; i++ {
if !suspicious[i] && !vis[i] {
dfs2(i)
}
}
var ans []int
for i := 0; i < n; i++ {
if !suspicious[i] {
ans = append(ans, i)
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Graph Reachability Using DFS | Time Complexity: O(n + m), where n is the number of methods and m is the number of invocations. Space Complexity: O(n + m) for the graph representation. |
| Graph Reachability Using BFS | Time Complexity: O(n + m), due to graph traversal with BFS. Space Complexity: O(n + m), used for storing adjacency lists and BFS queue. |
| Two DFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Graph Reachability Using DFS | O(n + m) | O(n + m) | Standard solution when recursion depth is manageable and you want concise traversal logic |
| Graph Reachability Using BFS | O(n + m) | O(n + m) | When avoiding recursion or when iterative queue-based traversal is preferred |
Frequently asked questions
Is Remove Methods From Project easy or hard?
Remove Methods From Project is generally classified as a Medium problem. The main challenge is recognizing the dependency structure as a directed graph and verifying that removing a reachable component does not break external dependencies.
Remove Methods From Project Python/Java solution
Most implementations build an adjacency list and perform DFS or BFS to find all methods reachable from the suspicious one. The same logic works across languages such as Python, JavaScript, C, and C++, with time complexity O(n + m) and linear space usage.
How to solve Remove Methods From Project in O(n + m)?
Build an adjacency list for the method call graph and run a DFS or BFS starting from the suspicious method. Mark all reachable nodes as potentially removable. After traversal, check whether any edge originates from a non-reachable node and points into the reachable set. If that happens, removal is invalid; otherwise return all non-reachable methods.
What is the best approach for Remove Methods From Project?
The optimal approach is graph reachability using DFS or BFS. Treat methods as nodes in a directed graph and method calls as edges. Traverse from the suspicious method to mark all reachable methods, then verify that no method outside this set calls any of them. This runs in O(n + m) time where n is the number of methods and m is the number of call relationships.
Is Remove Methods From Project asked at Google/Amazon/Meta?
Problems involving dependency graphs and reachability appear frequently in interviews at companies like Google, Amazon, and Meta. Variations often involve detecting affected modules, pruning dependency chains, or validating safe removals in directed graphs.
What data structure is used in Remove Methods From Project?
The core data structure is a directed graph represented with an adjacency list. A visited set or boolean array tracks reachable methods, and either a recursion stack (DFS) or queue (BFS) performs the traversal.
What is the time complexity of Remove Methods From Project?
Both DFS and BFS solutions run in O(n + m) time because each method (node) and call relationship (edge) is processed at most once during traversal and validation. The space complexity is also O(n + m) due to the adjacency list and visited set.