1059MediumHash TableTreeDepth-First SearchBreadth-First SearchDP on Trees

Visiting Every Marked Junction and Returning

Tracked in this browser only

Trains the technique from

LeetCode 1443Minimum Time to Collect All Apples in a Tree

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 network of n junctions numbered 0 through n - 1 is joined by the pipes pipes, one fewer pipe than there are junctions, with every junction reachable from every other and no loop anywhere. Walking a pipe takes one second, either way.

marked[i] says whether junction i needs visiting.

Start at junction 0, visit every marked junction, and return to junction 0. Return the fewest seconds it takes.

Examples

Example 1

Input: n = 4, pipes = [[0, 1], [1, 2], [0, 3]], marked = [false, false, true, false]
Output: 4

Only junction 2 is marked, and reaching it means walking two pipes out and the same two back. The pipe to junction 3 has nothing marked beyond it and is never walked.

Example 2

Input: n = 3, pipes = [[0, 1], [0, 2]], marked = [false, true, true]
Output: 4

Both junctions hanging off the start are marked, so each of the two pipes is walked out and back.

Example 3

Input: n = 1, pipes = [], marked = [true]
Output: 0

The one junction is where the walk starts, so it is already visited and nothing needs walking.

Constraints

1 <= n <= 10^5
pipes.length == n - 1
pipes[i].length == 2
0 <= pipes[i][j] <= n - 1
The two ends of a pipe are different junctions.
marked.length == n

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 min_time(n: int, pipes: list[list[int]], marked: list) -> int:

Java

public int minTime(int n, int[][] pipes, boolean[] marked)

The intended approach

Time O(n) over the junctions and pipes.Space O(n) for the neighbour lists and the walk.

Hang the network from junction `0`. Then each pipe has a near end and a far end, and everything beyond the far end can only be reached through that pipe, since the network holds no loop. So a pipe has to be walked exactly twice, once out and once back, precisely when something marked lies beyond its far end; and it need never be walked at all otherwise. Twice, not more, because a single excursion can pick up everything beyond that pipe before returning. That turns the answer into a count: two seconds for every pipe with a marked junction somewhere beyond it. Settle it from the leaves upward, carrying for each junction whether anything marked sits at or below it, and adding two for each pipe down to a junction that carries a mark. Junction `0` itself being marked costs nothing, since the walk starts there. One walk over the network, done with an explicit stack so a long thin network cannot exhaust the call depth.

Pythonentry point: min_time

def min_time(n, pipes, marked):
    near = [[] for _ in range(n)]
    for pipe in pipes:
        near[pipe[0]].append(pipe[1])
        near[pipe[1]].append(pipe[0])
    parent = [-1] * n
    order = [0]
    seen = [False] * n
    seen[0] = True
    stack = [0]
    while stack:
        here = stack.pop()
        for there in near[here]:
            if not seen[there]:
                seen[there] = True
                parent[there] = here
                order.append(there)
                stack.append(there)
    carries = [False] * n
    for at in range(n):
        carries[at] = bool(marked[at])
    total = 0
    for at in range(len(order) - 1, 0, -1):
        node = order[at]
        if carries[node]:
            total += 2
            carries[parent[node]] = True
    return total

The obvious version

Gather the pipes that have to be walked instead of counting them. For every marked junction, climb from it back to junction `0` one pipe at a time, adding each pipe climbed to a collection, so a pipe shared by several junctions lands in the collection once. Twice the size of the collection is the answer. Costs a climb per marked junction rather than one walk over the network.

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_min_time(n, pipes, marked):
    from collections import deque
    near = [[] for _ in range(n)]
    for pipe in pipes:
        near[pipe[0]].append(pipe[1])
        near[pipe[1]].append(pipe[0])
    parent = [-1] * n
    seen = [False] * n
    seen[0] = True
    queue = deque([0])
    while queue:
        here = queue.popleft()
        for there in near[here]:
            if not seen[there]:
                seen[there] = True
                parent[there] = here
                queue.append(there)
    used = set()
    for at in range(n):
        if not marked[at]:
            continue
        node = at
        while node != 0:
            up = parent[node]
            used.add((up, node))
            node = up
    return 2 * len(used)

How this problem was checked

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