Remove Methods From Project

Medium
1724.

Remove Methods From Project

Remove Methods From Project is a medium coding problem on depth-first search, breadth-first search and graph, asked in Amazon interviews.

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^5
  • 0 <= k <= n - 1
  • 0 <= invocations.length <= 2 * 10^5
  • invocations[i] == [ai, bi]
  • 0 <= ai, bi <= n - 1
  • ai != bi
  • invocations[i] != invocations[j] for i != j
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number} k
 * @param {number[][]} invocations
 * @return {number[]}
 */
var remainingMethods = function(n, k, invocations) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^5
  • 0 <= k <= n - 1
  • 0 <= invocations.length <= 2 * 10^5
  • invocations[i] == [ai, bi]
  • 0 <= ai, bi <= n - 1
  • ai != bi
  • invocations[i] != invocations[j] for i != j

Hints for Remove Methods From Project

  1. Hint 1

    First find the suspicious group: every method reachable from k along the call edges.

  2. Hint 2

    A BFS or DFS from k over the directed edges marks the group in O(n + m).

  3. Hint 3

    Then scan every call a → b: if a is outside the group and b inside 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

  1. Build the directed adjacency lists of the calls.
  2. BFS from k, marking every method reached as suspicious.
  3. For each call [a, b], if a is not suspicious but b is, return every method 0 … n - 1.
  4. 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 k is 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)