We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Remove Methods From Project

Number: 3561

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

You are given n methods (numbered from 0 to n - 1) and an integer k where method k has a known bug. Every invocation relationship is given in the 2D array invocations where an edge [a, b] means method a calls method b. Any method that is either k or invoked (directly or indirectly) by k is considered suspicious. However, a group of suspicious methods may only be completely removed if no method outside the group calls a method inside the group. Return an array of methods remaining after removing the suspicious ones if removal can be performed; otherwise, return all methods.

Key Insights

  • Use graph traversal (DFS or BFS) starting from k to identify all suspicious methods.
  • The directed relationships form a graph; traversing from k marks all methods it can reach.
  • Check for any invocation edge from a non-suspicious method into a suspicious one. If such an edge exists, removal is not allowed.
  • If removal is valid, output all methods that are not suspicious; if not, return the entire list of methods.

Space and Time 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) to store the graph and additional data structures used for traversal.

Solution

The approach involves two main phases:

  1. Graph Traversal: Build an adjacency list from the invocations and perform a BFS (or DFS) beginning from node k to mark all suspicious methods.
  2. Validation and Removal: Iterate over each invocation. If any invocation goes from a non-suspicious method to a suspicious method, removal isn’t allowed. Otherwise, filter out the suspicious methods and return the remaining methods.

Key data structures include:

  • A graph (adjacency list) to represent the method call relationships.
  • A set or boolean array to keep track of suspicious methods.
  • A queue (for BFS) to traverse the graph from k.

This method ensures that you efficiently find suspicious methods and quickly determine if removal is feasible.

Code Solutions

from collections import deque, defaultdict

class Solution:
    def removeMethods(self, n: int, k: int, invocations: List[List[int]]) -> List[int]:
        # Build the graph using an adjacency list
        graph = defaultdict(list)
        for caller, callee in invocations:
            graph[caller].append(callee)
        
        # Use BFS to find all suspicious methods starting from k
        suspicious = set()
        queue = deque([k])
        while queue:
            method = queue.popleft()
            if method in suspicious:
                continue
            suspicious.add(method)
            for next_method in graph[method]:
                if next_method not in suspicious:
                    queue.append(next_method)
        
        # Validate removal: check if any method outside suspicious calls a suspicious method
        for caller, callee in invocations:
            if caller not in suspicious and callee in suspicious:
                # If such an edge exists, removal is invalid; return all methods.
                return list(range(n))
        
        # Removal valid; return non-suspicious methods.
        return [method for method in range(n) if method not in suspicious]
← Back to All Questions