Facebook Pixel

3310. Remove Methods From Project

MediumDepth-First SearchBreadth-First SearchGraph
Leetcode Link

Problem Description

In this problem, you are managing a project with n methods numbered from 0 to n - 1. You have two integers n and k, along with a 2D integer array named invocations. This array represents method calls where invocations[i] = [a_i, b_i] means method a_i invokes method b_i.

A bug is discovered in method k, and any method it calls directly or indirectly is deemed suspicious. The aim is to remove all suspicious methods. However, you can only remove a group of methods if no method outside this group invokes any method within it. The task is to return a list of remaining methods after removing suspicious ones. The methods can be returned in any order. If it is not feasible to remove all suspicious methods, then none should be removed.

Intuition

To solve this problem, we need to identify all methods that are considered suspicious because they can invoke method k, either directly or indirectly. We use a graph representation to track method invocations: each method is a node, and an invocation from one method to another is a directed edge.

Steps to Approach the Solution

  1. Discover Suspicious Methods:

    • Use Depth-First Search (DFS) starting from method k to find all methods that are directly or indirectly invoked by it. These methods are marked as suspicious.

  2. Identify Non-Suspicious Groups:

    • Traverse through all methods that are not marked as suspicious. For each non-suspicious method that hasn't been visited yet, perform another DFS to mark all connected methods reachable from it as non-suspicious. This includes methods which no suspicious methods can invoke.

  3. Collect Remaining Methods:

    • Finally, compile a list of methods that are confirmed not to be suspicious and can safely be retained in the project.

This two-step approach effectively isolates groups of methods, ensuring that only those that can be removed without violating the conditions are considered, and provides the desired list of methods that remain in the project after cleanup.

Learn more about Depth-First Search, Breadth-First Search and Graph patterns.

Solution Approach

The solution strategy involves using two Depth-First Search (DFS) traversals over method invocations. Here's how we implement it:

  1. Graph Construction:

    • We construct two types of graphs from the invocations array.
      • g: A direct invocation graph where each method points to another method it invokes.
      • f: An undirected graph to efficiently check connectivity among methods.
    • For each invocation [a, b] in invocations, add b to the adjacency list of a in g, and both ways in f to ensure bi-directional traversal.

  2. First DFS for Identifying Suspicious Methods:

    • Initialize a boolean array suspicious to keep track of methods starting from k that are directly or indirectly reachable.
    • Perform a DFS from method k using graph g, marking all reachable nodes as suspicious.
    def dfs(i: int):
    suspicious[i] = True
    for j in g[i]:
        if not suspicious[j]:
            dfs(j)

    This marks every node that k can reach as suspicious.

  3. Second DFS for Marking Non-Suspicious Methods:

    • Initialize another boolean array vis to track visited methods during this phase.
    • Traverse each method, and for methods not marked suspicious, perform a DFS using graph f. This DFS marks connected components of non-suspicious methods, preventing them from being marked suspicious inadvertently.
    def dfs2(i: int):
    vis[i] = True
    for j in f[i]:
        if not vis[j]:
            suspicious[j] = False
            dfs2(j)

    This step ensures methods not reachable by k and its chain of invocations can be validated independently.

  4. Gathering Results:

    • Collect and return all methods that aren't suspicious.
    return [i for i in range(n) if not suspicious[i]]

This thorough two-phase DFS approach leverages graph traversal to segregate suspicious methods from the rest while maintaining validity constraints, ensuring that only perfectly isolated groups of suspicious methods are removed, resulting in the correct list of remaining methods.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Suppose n = 5, k = 2, and the invocations array is as follows:

invocations = [
    [0, 1],
    [1, 2],
    [2, 3],
    [3, 4]
]

Here, method k = 2 is the bugged method. Our goal is to identify all methods that directly or indirectly invoke or are invoked by method 2, classifying them as suspicious, and then determine if they can be removed safely.

Step-by-Step Execution

  1. Graph Construction:

    • Construct the direct invocation graph g:
      • g represents the following connections:
        • 0 -> 1
        • 1 -> 2
        • 2 -> 3
        • 3 -> 4
    • Construct the undirected graph f for checking reachability:
      • f will have bi-directional connections:
        • 0 <-> 1
        • 1 <-> 2
        • 2 <-> 3
        • 3 <-> 4

  2. First DFS to Identify Suspicious Methods:

    • Start DFS from method k = 2 in graph g:
      • Mark method 2 as suspicious.
      • Traverse from method 2 to 3 and mark it as suspicious.
      • Traverse from method 3 to 4 and mark it as suspicious.
    • Suspicious methods after first DFS: [2, 3, 4]

  3. Second DFS to Identify Safe Methods:

    • Traverse each method that is not suspicious:
      • Start from method 0 in graph f:
        • Mark method 0 as visited and non-suspicious since it's not reachable by method 2.
        • Continue to method 1, marking it non-suspicious as well.

Methods 0 and 1 form a part of the non-suspicious methods.

  1. Gather Remaining Methods:
    • Collect the methods that are not suspicious: [0, 1]

This approach effectively separates suspicious and non-suspicious methods and validates their segregation before determining which ones can remain.

Final list of methods that can remain in the project: [0, 1]

Solution Implementation

1from typing import List
2
3class Solution:
4    def remainingMethods(self, n: int, k: int, invocations: List[List[int]]) -> List[int]:
5        # Depth-First Search (DFS) to mark suspicious methods
6        def dfs(i: int):
7            suspicious[i] = True
8            for j in graph_out[i]:
9                if not suspicious[j]:
10                    dfs(j)
11
12        # Another DFS to mark safe methods
13        def dfs2(i: int):
14            visited[i] = True
15            for j in graph_bi[i]:
16                if not visited[j]:
17                    suspicious[j] = False
18                    dfs2(j)
19
20        # Create adjacency lists for the graph
21        graph_bi = [[] for _ in range(n)]  # Bidirectional connections
22        graph_out = [[] for _ in range(n)]  # Unidirectional connections (outgoing)
23
24        # Build the graphs based on invocations
25        for a, b in invocations:
26            graph_bi[a].append(b)
27            graph_bi[b].append(a)
28            graph_out[a].append(b)
29
30        # Initialize suspicious methods array
31        suspicious = [False] * n
32        # Start DFS from the method `k` to find all suspicious methods
33        dfs(k)
34
35        # Initialize visited array to track safe methods
36        visited = [False] * n
37        # List to store result
38        result = []
39      
40        # Check all methods for safety
41        for i in range(n):
42            if not suspicious[i] and not visited[i]:
43                # Perform DFS to mark connected safe methods
44                dfs2(i)
45
46        # Collate remaining safe methods
47        return [i for i in range(n) if not suspicious[i]]
48
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5class Solution {
6    private boolean[] suspicious;  // Array to track suspicious methods
7    private boolean[] visited;     // Array to track visited methods
8    private List<Integer>[] forwardGraph;  // Directed graph
9    private List<Integer>[] undirectedGraph; // Undirected graph
10
11    public List<Integer> remainingMethods(int n, int k, int[][] invocations) {
12        suspicious = new boolean[n];
13        visited = new boolean[n];
14        forwardGraph = new List[n];
15        undirectedGraph = new List[n];
16
17        // Initialize graph structures
18        Arrays.setAll(forwardGraph, i -> new ArrayList<>());
19        Arrays.setAll(undirectedGraph, i -> new ArrayList<>());
20
21        // Fill graph with given invocations
22        for (int[] invocation : invocations) {
23            int u = invocation[0], v = invocation[1];
24            forwardGraph[u].add(v);
25            undirectedGraph[u].add(v);
26            undirectedGraph[v].add(u);
27        }
28
29        // Mark all reachable nodes from starting node k in the directed graph
30        dfs(k);
31
32        // Explore all components and mark them if they are not suspicious
33        for (int i = 0; i < n; ++i) {
34            if (!suspicious[i] && !visited[i]) {
35                dfs2(i);
36            }
37        }
38
39        // Collect non-suspicious methods for the result
40        List<Integer> result = new ArrayList<>();
41        for (int i = 0; i < n; ++i) {
42            if (!suspicious[i]) {
43                result.add(i);
44            }
45        }
46        return result;
47    }
48
49    private void dfs(int node) {
50        suspicious[node] = true;
51        for (int neighbor : forwardGraph[node]) {
52            if (!suspicious[neighbor]) {
53                dfs(neighbor);
54            }
55        }
56    }
57
58    private void dfs2(int node) {
59        visited[node] = true;
60        for (int neighbor : undirectedGraph[node]) {
61            if (!visited[neighbor]) {
62                suspicious[neighbor] = false;
63                dfs2(neighbor);
64            }
65        }
66    }
67}
68
1#include <vector>
2
3using namespace std;
4
5class Solution {
6public:
7    vector<int> remainingMethods(int n, int k, vector<vector<int>>& invocations) {
8        vector<bool> isSuspicious(n, false);  // Tracks if a method is suspicious
9        vector<bool> visited(n, false);       // Tracks if a method has been visited
10        vector<vector<int>> bidirectionalGraph(n); // Graph with undirected edges
11        vector<vector<int>> directedGraph(n); // Graph with directed edges
12      
13        // Building both graphs based on invocations
14        for (const auto& invocation : invocations) {
15            int a = invocation[0];
16            int b = invocation[1];
17            bidirectionalGraph[a].push_back(b);
18            bidirectionalGraph[b].push_back(a);
19            directedGraph[a].push_back(b);
20        }
21      
22        // Depth-First Search to mark all suspicious methods
23        auto dfsSuspicious = [&](auto&& self, int i) -> void {
24            isSuspicious[i] = true;
25            for (int neighbor : directedGraph[i]) {
26                if (!isSuspicious[neighbor]) {
27                    self(self, neighbor);
28                }
29            }
30        };
31      
32        // Start DFS from method `k` to find all suspicious methods
33        dfsSuspicious(dfsSuspicious, k);
34      
35        // Depth-First Search to remove suspicion from connected components
36        auto dfsClearSuspicion = [&](auto&& self, int i) -> void {
37            visited[i] = true;
38            for (int neighbor : bidirectionalGraph[i]) {
39                if (!visited[neighbor]) {
40                    isSuspicious[neighbor] = false;
41                    self(self, neighbor);
42                }
43            }
44        };
45      
46        // Iterate through all methods to clear suspicion from unvisited methods
47        for (int i = 0; i < n; ++i) {
48            if (!isSuspicious[i] && !visited[i]) {
49                dfsClearSuspicion(dfsClearSuspicion, i);
50            }
51        }
52      
53        // Collect methods that are not suspicious
54        vector<int> result;
55        for (int i = 0; i < n; ++i) {
56            if (!isSuspicious[i]) {
57                result.push_back(i);
58            }
59        }
60      
61        return result;
62    }
63};
64
1// Function to find which methods do not appear suspicious based on invocations.
2function remainingMethods(n: number, k: number, invocations: number[][]): number[] {
3    // Array to track suspicious methods, initially all set to false.
4    const suspiciousMethods: boolean[] = Array(n).fill(false);
5    // Array to track visited methods, initially all set to false.
6    const visited: boolean[] = Array(n).fill(false);
7    // 'f' represents adjacency list for an undirected graph.
8    const undirectedAdjacencyList: number[][] = Array.from({ length: n }, () => []);
9    // 'g' represents adjacency list for a directed graph.
10    const directedAdjacencyList: number[][] = Array.from({ length: n }, () => []);
11
12    // Construct the adjacency lists based on the invocations.
13    for (const [a, b] of invocations) {
14        undirectedAdjacencyList[a].push(b);
15        undirectedAdjacencyList[b].push(a);
16        directedAdjacencyList[a].push(b);
17    }
18
19    // Depth-first search to mark methods reachable from method 'k' as suspicious.
20    const markSuspicious = (index: number) => {
21        suspiciousMethods[index] = true;
22        for (const neighbor of directedAdjacencyList[index]) {
23            if (!suspiciousMethods[neighbor]) {
24                markSuspicious(neighbor);
25            }
26        }
27    };
28
29    // Initialize DFS from method 'k' to mark suspicious methods.
30    markSuspicious(k);
31
32    // Depth-first search to clear suspicion from certain methods.
33    const clearSuspicion = (index: number) => {
34        visited[index] = true;
35        for (const neighbor of undirectedAdjacencyList[index]) {
36            if (!visited[neighbor]) {
37                suspiciousMethods[neighbor] = false;
38                clearSuspicion(neighbor);
39            }
40        }
41    };
42
43    // Explore each method to clear suspicion from fully connected components.
44    for (let i = 0; i < n; i++) {
45        if (!suspiciousMethods[i] && !visited[i]) {
46            clearSuspicion(i);
47        }
48    }
49
50    // Return the indices of methods that are not suspicious.
51    return Array.from({ length: n }, (_, i) => i).filter(i => !suspiciousMethods[i]);
52}
53

Time and Space Complexity

The time complexity of the code is O(n + m), where n is the number of methods and m is the number of call relationships. This accounts for performing a depth-first search (DFS) across all nodes and edges present in the graph representation of method invocations.

The space complexity is O(n + m), due to the space required for the adjacency list representations f and g, which together store an edge for each method invocation relationship, leading to m relationships in the worst case. Additionally, the space for auxiliary lists suspicious and vis, both of size n, contributes to the space complexity.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Recommended Readings

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Graph Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More