0470MediumArrayHash TableTreeBinary Tree

Retracing the Heating Network

Tracked in this browser only

Trains the technique from

LeetCode 2196Create Binary Tree From Descriptions

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 survey crew has re-traced a district heating network one connection at a time, in no particular order. Each note links[i] = [upstream_i, downstream_i, tap_i] says that valve downstream_i hangs directly off valve upstream_i: off that valve's left tap when tap_i is 1, and off its right tap when tap_i is 0.

Valve ids are distinct positive integers. Every valve has at most one valve on its left tap and at most one on its right tap, and the notes together describe a single network with exactly one valve at the top, which is the one no note ever lists as a downstream valve.

Rebuild the network and return it as a flat listing, laid out by this rule and no other. Put the top valve into a waiting line on its own. Then repeatedly take the valve at the front of the line: write its id at the end of the listing, then add to the back of the line what sits on its left tap and then what sits on its right tap, adding the marker null for a tap with nothing on it. When null reaches the front of the line, write null to the listing and add nothing. Stop when the line runs dry, then delete any null entries left sitting after the last valve id in the listing.

Examples

Example 1

Input: links = [[41, 27, 1], [41, 58, 0]]
Output: [41, 27, 58]

Valve 41 is the only one no note feeds. It carries 27 on its left tap and 58 on its right, and both of those have nothing hanging off them, so the listing ends there.

Example 2

Input: links = [[3, 8, 0], [19, 3, 1], [19, 44, 0], [8, 5, 1]]
Output: [19, 3, 44, null, 8, null, null, 5]

Valve 19 is at the top even though it appears in the second note. Valve 3 has an empty left tap, which shows up as a `null` inside the listing rather than at the end.

Example 3

Input: links = [[9, 4, 1], [4, 2, 1], [2, 61, 1]]
Output: [9, 4, null, 2, null, 61]

Every connection here uses a left tap, so each valve leaves a `null` behind for the right tap it never fills, and only the run of `null` markers past the last id is deleted.

Constraints

1 <= links.length <= 10^4
links[i].length == 3
1 <= upstream_i, downstream_i <= 10^5
0 <= tap_i <= 1
The notes describe a valid network: one top valve, at most one valve per tap, and no cycles.

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 rebuild_network(links: list[list[int]]) -> list:

Java

public List<Integer> rebuildNetwork(int[][] links)

The intended approach

Time O(n) for n notesSpace O(n) for the tap tables, the id sets, the queue and the returned listing

Make one pass over the notes to fill two tables, one per tap, keyed by the upstream valve, while collecting the set of every id mentioned and the set of ids that appear as a downstream valve. The single id in the first set but not the second is the top of the network. Then run the listing rule literally with a queue, looking each tap up in its table and queueing `None` for a tap with nothing on it, and trim the trailing markers at the end.

Pythonentry point: rebuild_network

from collections import deque


def rebuild_network(links):
    # time O(n) over the notes plus O(n) to lay the listing out
    # space O(n) for the two tap tables, the id sets and the queue
    left = {}
    right = {}
    mentioned = set()
    fed = set()
    for note in links:
        up, down, tap = note[0], note[1], note[2]
        mentioned.add(up)
        mentioned.add(down)
        fed.add(down)
        if tap == 1:
            left[up] = down
        else:
            right[up] = down
    top = None
    for valve in mentioned:
        if valve not in fed:
            top = valve
            break
    listing = []
    queue = deque([top])
    while queue:
        valve = queue.popleft()
        if valve is None:
            listing.append(None)
            continue
        listing.append(valve)
        queue.append(left.get(valve))
        queue.append(right.get(valve))
    while listing and listing[-1] is None:
        listing.pop()
    return listing

The obvious version

Collect the ids by linear membership tests on a list, then find the top valve by testing each id against every note to see whether anything feeds it. Lay the listing out one whole row of the network at a time, re-scanning all the notes to find each valve's two taps.

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_rebuild_network(links):
    ids = []
    for note in links:
        for valve in (note[0], note[1]):
            if valve not in ids:
                ids.append(valve)
    top = None
    for valve in ids:
        downstream_of_something = False
        for note in links:
            if note[1] == valve:
                downstream_of_something = True
                break
        if not downstream_of_something:
            top = valve
            break
    listing = []
    row = [top]
    while row:
        nxt = []
        for valve in row:
            if valve is None:
                listing.append(None)
                continue
            listing.append(valve)
            lo = None
            ro = None
            for note in links:
                if note[0] == valve and note[2] == 1:
                    lo = note[1]
                if note[0] == valve and note[2] == 0:
                    ro = note[1]
            nxt.append(lo)
            nxt.append(ro)
        row = nxt
    while listing and listing[-1] is None:
        listing.pop()
    return listing

How this problem was checked

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