3310. Remove Methods From Project

Array
DFS
BFS
Graph

TIME

O(n + m)

SPACE

O(n + m)

Intuition

The suspicious set is everything reachable from k along the invocation edges (directed graph). Those can be removed only if nothing outside the set calls into it, otherwise removing them would break a caller. If even one external caller points in, the rule forbids removal, so we keep everything.

Approach

Build the directed adjacency list from invocations.
Mark suspicious: BFS/DFS from k, marking every reachable method.
Safety check: scan all edges a -> b; if some a is not suspicious but b is, an outside method invokes the group → removal impossible → return all methods 0..n-1.
Otherwise return every method not marked suspicious.

Complexity

Time: O(n + m), traversal plus one edge scan
Space: O(n + m), adjacency list and visited array

Edge Cases

External caller into the suspicious set (Example 1) → return everything
Suspicious set fully self-contained (Examples 2, 3) → remove it
All methods suspicious → return empty list
No invocations → only k is suspicious, and no external caller exists → remove just k
Cycles among suspicious methods → handled by the visited marking

Code

from typing import List
from collections import deque


class Solution:
    def remainingMethods(self, n: int, k: int, invocations: List[List[int]]) -> List[int]:
        """
        3310. Remove Methods From Project
        Time: O(n + m)
        Space: O(n + m)
        """
        adj = [[] for _ in range(n)]
        for a, b in invocations:
            adj[a].append(b)

        # Mark all methods reachable from k (the suspicious set).
        suspicious = [False] * n
        suspicious[k] = True
        dq = deque([k])
        while dq:
            u = dq.popleft()
            for v in adj[u]:
                if not suspicious[v]:
                    suspicious[v] = True
                    dq.append(v)

        # If any non-suspicious method invokes a suspicious one, we can't remove.
        for a, b in invocations:
            if not suspicious[a] and suspicious[b]:
                return list(range(n))

        return [m for m in range(n) if not suspicious[m]]

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

/**
 * 3310. Remove Methods From Project
 * Time: O(n + m)
 * Space: O(n + m)
 */
class Solution {
    public List<Integer> remainingMethods(int n, int k, int[][] invocations) {
        List<Integer>[] adj = new List[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] e : invocations) {
            adj[e[0]].add(e[1]);
        }

        // Mark all methods reachable from k (the suspicious set).
        boolean[] suspicious = new boolean[n];
        suspicious[k] = true;
        ArrayDeque<Integer> dq = new ArrayDeque<>();
        dq.add(k);
        while (!dq.isEmpty()) {
            int u = dq.poll();
            for (int v : adj[u]) {
                if (!suspicious[v]) {
                    suspicious[v] = true;
                    dq.add(v);
                }
            }
        }

        // If any non-suspicious method invokes a suspicious one, we can't remove.
        List<Integer> result = new ArrayList<>();
        for (int[] e : invocations) {
            if (!suspicious[e[0]] && suspicious[e[1]]) {
                for (int i = 0; i < n; i++) {
                    result.add(i);
                }
                return result;
            }
        }

        for (int m = 0; m < n; m++) {
            if (!suspicious[m]) {
                result.add(m);
            }
        }
        return result;
    }
}