0258HardDynamic ProgrammingTreeDepth-First SearchBinary TreeDP on Trees

Fewest Duct Sensors

Tracked in this browser only

Trains the technique from

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.

An air-duct network runs out from a single plant-room junction. Every junction splits into at most two junctions further along the network, one on its left branch and one on its right branch.

Because the harness passes plain JSON, the network arrives as junctions, a listing written depth by depth. junctions[0] stands for the plant-room junction. After it the entries come in pairs, giving the left branch and then the right branch of each junction already written out, taken in that same order. A branch that carries no junction is written null, and a null claims no pair of its own; trailing null entries are left off the end. Only the shape of the network matters here, so every entry that stands for a junction is written 0.

A sensor fitted at a junction watches that junction, the junction immediately upstream of it, and every junction immediately downstream of it. Nothing further away is watched.

Return the fewest sensors that leave every junction in the network watched.

Examples

Example 1

Input: junctions = [0, 0, null, 0]
Output: 1

The network is a chain of three junctions. A sensor at the middle one watches the plant-room junction upstream of it, itself, and the junction downstream of it, so one sensor covers all three.

Example 2

Input: junctions = [0]
Output: 1

A lone junction still has to be watched, and the only place to fit a sensor is that junction itself.

Example 3

Input: junctions = [0, 0, null, 0, null, 0]
Output: 2

The network is a chain of four junctions. A sensor on the second junction watches the first three, and a sensor on the fourth watches itself, which leaves nothing unwatched.

Constraints

1 <= number of junctions <= 1000
Every entry of junctions is either 0 or null
junctions[0] == 0
1 <= junctions.length <= 2001

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 fewest_sensors(junctions: list) -> int:

Java

public int fewestSensors(Integer[] junctions)

The intended approach

Time O(n) for n junctions: each listing entry is consumed once and each junction is settled once.Space O(n) for the rebuilt network, the marks and the stack.

Rebuild the network from the listing, then settle the junctions furthest out first, giving each one of three marks: unwatched, watched from a sensor downstream, or holding a sensor. A junction with an unwatched junction downstream must take a sensor, since only its own sensor can still reach that junction; otherwise it is watched when some junction downstream holds a sensor, and unwatched when neither applies, leaving the junction upstream to deal with it. The plant-room junction has nothing upstream, so a sensor is added there if it ends up unwatched. The sweep runs off an explicit stack, because a network of a thousand junctions can form a single chain.

Pythonentry point: fewest_sensors

def fewest_sensors(junctions):
    if not junctions or junctions[0] is None:
        return 0
    downstream = [[]]
    listed = 0
    at = 1
    while listed < len(downstream) and at < len(junctions):
        for _ in range(2):
            if at >= len(junctions):
                break
            entry = junctions[at]
            at += 1
            if entry is not None:
                downstream.append([])
                downstream[listed].append(len(downstream) - 1)
        listed += 1

    # 0 = still uncovered, 1 = covered by a sensor downstream, 2 = holds a sensor
    BARE, COVERED, FITTED = 0, 1, 2
    mark = [BARE] * len(downstream)
    fitted = 0
    # post-order from an explicit stack: a chain of 1000 junctions would blow
    # the interpreter's recursion limit
    stack = [(0, False)]
    while stack:
        node, settled = stack.pop()
        if not settled:
            stack.append((node, True))
            for child in downstream[node]:
                stack.append((child, False))
            continue
        needs = False
        shielded = False
        for child in downstream[node]:
            if mark[child] == BARE:
                needs = True
            elif mark[child] == FITTED:
                shielded = True
        if needs:
            mark[node] = FITTED
            fitted += 1
        elif shielded:
            mark[node] = COVERED
        else:
            mark[node] = BARE
    if mark[0] == BARE:
        fitted += 1
    return fitted

The obvious version

Try every set of junctions: mark what each chosen sensor watches, keep the sets that leave nothing unwatched, and report the smallest. O(2^n * n).

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_fewest_sensors(junctions):
    if not junctions or junctions[0] is None:
        return 0
    downstream = [[]]
    upstream = [-1]
    listed = 0
    at = 1
    while listed < len(downstream) and at < len(junctions):
        for _ in range(2):
            if at >= len(junctions):
                break
            entry = junctions[at]
            at += 1
            if entry is not None:
                downstream.append([])
                upstream.append(listed)
                downstream[listed].append(len(downstream) - 1)
        listed += 1
    total = len(downstream)
    best = total
    for choice in range(1 << total):
        covered = [False] * total
        fitted = 0
        for node in range(total):
            if choice >> node & 1:
                fitted += 1
                covered[node] = True
                if upstream[node] != -1:
                    covered[upstream[node]] = True
                for child in downstream[node]:
                    covered[child] = True
        if fitted < best and all(covered):
            best = fitted
    return best

How this problem was checked

Reference solution executed against 11 test cases — 11 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