0527MediumDepth-First SearchBreadth-First SearchGraph Theory

Pruning a Faulty Module and Its Imports

Tracked in this browser only

Trains the technique from

LeetCode 3310Remove Methods From Project

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A codebase has count modules, numbered 0 through count - 1. The import graph is given as a list of directed pairs: imports[i] = [a, b] means module a imports module b. A module never imports itself and no pair is listed twice.

Module faulty has been found broken. A cleanup marks faulty together with every module that can be reached from it by following one or more imports, since those are only pulled in on its account.

The cleanup is only safe if nothing outside the marked group depends on it. So if any module that is not marked imports a module that is marked, the cleanup is called off and every module stays. Otherwise all the marked modules are deleted.

Return the numbers of the modules still in the codebase afterwards, in increasing order.

Examples

Example 1

Input: count = 5, faulty = 0, imports = [[0, 1], [1, 2], [3, 4]]
Output: [3, 4]

Following imports from module 0 reaches modules 1 and 2, so the marked group is 0, 1 and 2. The only other pair is [3, 4], whose importer and target are both unmarked, so the cleanup goes ahead and modules 3 and 4 remain.

Example 2

Input: count = 5, faulty = 1, imports = [[0, 1], [1, 2], [2, 3]]
Output: [0, 1, 2, 3, 4]

The marked group is 1, 2 and 3. Module 0 is not marked and it imports module 1, which is, so the cleanup is called off and all five modules stay.

Example 3

Input: count = 3, faulty = 2, imports = []
Output: [0, 1]

With no imports at all the marked group is just module 2, and nothing depends on it, so modules 0 and 1 remain.

Constraints

1 <= count <= 10^5
0 <= faulty <= count - 1
0 <= imports.length <= 2 * 10^5
imports[i].length == 2
0 <= imports[i][0], imports[i][1] <= count - 1
imports[i][0] != imports[i][1]
No two entries of imports are the same pair.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def surviving_modules(count: int, faulty: int, imports: list[list[int]]) -> list[int]:

Java

public List<Integer> survivingModules(int count, int faulty, int[][] imports)

The intended approach

Time O(count + imports.length).Space O(count + imports.length) for the edge list, the marks and the stack.

Turn the pair list into an outgoing-edge list, then mark the group by walking forward from `faulty` with an explicit stack, so a chain of imports thousands of modules long is no problem. With the marks in place, one sweep of the pair list looks for a pair whose importer is unmarked while the module it imports is marked; finding one means every module stays. Otherwise collect the unmarked numbers, which come out in increasing order because they are gathered by index.

Pythonentry point: surviving_modules

def surviving_modules(count, faulty, imports):
    # O(count + edges): one walk from the faulty module driven by an explicit
    # stack, then a single sweep of the import list.
    out = [[] for _ in range(count)]
    for pair in imports:
        out[pair[0]].append(pair[1])
    marked = [False] * count
    marked[faulty] = True
    stack = [faulty]
    while stack:
        here = stack.pop()
        for there in out[here]:
            if not marked[there]:
                marked[there] = True
                stack.append(there)
    for pair in imports:
        if not marked[pair[0]] and marked[pair[1]]:
            return list(range(count))
    return [i for i in range(count) if not marked[i]]

The obvious version

Mark by repeated relaxation instead of walking: sweep the whole pair list over and over, marking the target of any pair whose source is already marked, and stop when a sweep changes nothing. Then apply the same safety check.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_surviving_modules(count, faulty, imports):
    marked = [False] * count
    marked[faulty] = True
    changed = True
    while changed:
        changed = False
        for pair in imports:
            if marked[pair[0]] and not marked[pair[1]]:
                marked[pair[1]] = True
                changed = True
    for pair in imports:
        if not marked[pair[0]] and marked[pair[1]]:
            return [i for i in range(count)]
    return [i for i in range(count) if not marked[i]]

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in