0214MediumTreeDepth-First SearchBinary Tree

Pipeline Stretch Tallies

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.

A slurry pipeline carries material away from a single intake and splits as it goes. Every station on the network shifts the line pressure by a signed figure in kilopascals: positive where a booster pump adds pressure, negative where a filter costs pressure.

The network is handed to you as stations, a listing of the network one depth at a time, left to right. Slot 0 holds the intake. Each station that appears in the listing claims the next two free slots for the lines leaving it, the left line first and the right line second. A slot holding null carries no station and claims no slots of its own. Trailing null slots may be left off, and an empty listing means nothing has been built.

A stretch is one or more stations read off by following the flow: it may begin at any station and every further step must move to a station directly downstream of the one before it. Two stretches count as different unless they cover exactly the same stations.

Given the integer target, return how many stretches have pressure shifts totalling exactly target.

Examples

Example 1

Input: stations = [5, 2, 5], target = 5
Output: 2

The intake alone shifts pressure by 5, and the station on the right line alone shifts it by 5. Both are stretches of one station, and no other stretch totals 5.

Example 2

Input: stations = [7, -4, null, 9, 2], target = 12
Output: 1

Slot 2 is empty, so the intake has one line leaving it, ending at -4, which itself feeds 9 and 2. The stretch 7, -4, 9 totals 12.

Example 3

Input: stations = [], target = 3
Output: 0

No station has been built, so there is no stretch to total.

Constraints

0 <= number of listed stations <= 1000
-10^9 <= station pressure shift <= 10^9
-1000 <= target <= 1000
stations[0] is not null whenever stations is non-empty
stations is a valid depth-by-depth listing of one connected network

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 pipeline_stretch_tallies(stations: list[int | None], target: int) -> int:

Java

public int pipelineStretchTallies(Integer[] stations, int target)

The intended approach

Time O(n)Space O(n)

Rebuild the downstream links from the depth-by-depth listing, then walk the network keeping the running total from the intake to the current station. Any stretch ending at the current station is the gap between two such running totals, so hold a tally of the totals recorded along the chain still open above the current station and add the tally kept for the value `target` below the current total. Each station's total is taken back out of the tally once both of its lines are finished, and the walk is driven from an explicit stack so a network 1000 deep cannot overflow the interpreter.

Pythonentry point: pipeline_stretch_tallies

def pipeline_stretch_tallies(stations, target):
    n = len(stations)
    if n == 0 or stations[0] is None:
        return 0
    left = [-1] * n
    right = [-1] * n
    order = [0]
    slot = 1
    head = 0
    while head < len(order):
        cur = order[head]
        head += 1
        if slot < n:
            if stations[slot] is not None:
                left[cur] = slot
                order.append(slot)
            slot += 1
        if slot < n:
            if stations[slot] is not None:
                right[cur] = slot
                order.append(slot)
            slot += 1
    tally = {0: 1}
    found = 0
    pending = [(0, 0, 0)]
    while pending:
        kind, a, b = pending.pop()
        if kind == 1:
            tally[a] -= 1
            continue
        run = b + stations[a]
        found += tally.get(run - target, 0)
        tally[run] = tally.get(run, 0) + 1
        pending.append((1, run, 0))
        if left[a] >= 0:
            pending.append((0, left[a], run))
        if right[a] >= 0:
            pending.append((0, right[a], run))
    return found

The obvious version

Start a fresh downstream walk at every station and add up the shifts step by step, scoring one for each prefix that hits the target. No running totals are shared between starts, so this costs O(n * depth).

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_stretch_tallies(stations, target):
    n = len(stations)
    if n == 0 or stations[0] is None:
        return 0
    kids = {}
    order = [0]
    slot = 1
    head = 0
    while head < len(order):
        cur = order[head]
        head += 1
        kids[cur] = []
        for _ in range(2):
            if slot < n:
                if stations[slot] is not None:
                    kids[cur].append(slot)
                    order.append(slot)
                slot += 1
    total = 0
    for start in order:
        walks = [(start, 0)]
        while walks:
            node, acc = walks.pop()
            acc += stations[node]
            if acc == target:
                total += 1
            for k in kids.get(node, []):
                walks.append((k, acc))
    return total

How this problem was checked

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