Watch 7 video solutions for Remove Methods From Project, a medium level problem involving Depth-First Search, Breadth-First Search, Graph. This walkthrough by Pretest Passed has 998 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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]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 | 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 |