Remove Methods From Project - Solution & Explanation
Problem Statement
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.
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.
Code
Python
JavaScript
Complexity
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.
This C solution uses BFS where suspicious methods are determined by traversing all nodes reachable from k, using a queue. A reverse graph helps identify and ensure no outgoing invocations exist from suspicious to non-suspicious methods. If such a path exists, returning null indicates impossibility; otherwise, non-suspicious methods are returned.
Complexity
Time Complexity: O(n + m), where n is the number of nodes and m is the number of invocations. Space Complexity: O(n + m), mainly for storing graphs and additional data structures.
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.
Code
Python
Java
C++
Go
TypeScript
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), where n is the number of nodes and m is the number of invocations. Space Complexity: O(n + m), mainly for storing graphs and additional data structures. |
| Two DFS | — |
Detailed 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 |
Video Solution
Leetcode | Weekly Contest 418 | 3312. Sorted GCD Pair Queries | 3310. Remove Methods From Project • Pretest Passed • 1,271 views views
Watch 6 more video solutions →Frequently Asked Questions
Is Remove Methods From Project easy or hard?
Remove Methods From Project Python/Java solution
How to solve Remove Methods From Project in O(n + m)?
What is the best approach for Remove Methods From Project?
Is Remove Methods From Project asked at Google/Amazon/Meta?
What data structure is used in Remove Methods From Project?
What is the time complexity of Remove Methods From Project?
Ready to solve this problem?
Practice Remove Methods From Project with our built-in code editor and test cases.
Practice on FleetCode