0991MediumHash TableTreeDepth-First SearchBinary Tree

Sections of a Rig That Have a Look-Alike

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 cargo rig is given as the flat list rig. It hangs from a single top joint, every joint carries at most two joints below it in a first and a second slot, and either slot may be empty.

A flat list is read level by level: its first entry is the top joint's load, and reading left to right, every entry that is not null claims the next two unused positions as its first and second slot in that order, while null marks an empty slot and claims no positions of its own. A list that ends early leaves the remaining slots empty. The position of a joint is where its load sits in the list.

A section of the rig is one joint together with everything hanging below it. Two sections are alike when they have the same shape and matching joints carry the same load.

Return the positions of the top joints of the sections that have a look-alike somewhere in the rig. Where several sections are alike, report only the earliest of their positions. List the positions in increasing order.

Examples

Example 1

Input: rig = [5, 4, 6, 7, null, 4, 7, null, null, 7]
Output: [1, 3]

Three joints loaded 7 hang with nothing below them, so all three of those sections are alike and the earliest sits at position 3. Higher up, the joint at position 1 and the joint at position 5 are both loaded 4 and both carry a single 7 in their first slot, so those two sections are alike as well and the earlier of them is at position 1.

Example 2

Input: rig = [1, 2, 2, 5, null, null, 5]
Output: [3]

The two joints loaded 5 hang bare and are alike, so position 3 is reported. The two joints loaded 2 are not alike, because one carries its 5 in the first slot and the other in the second, which is a different shape.

Example 3

Input: rig = [1, 4, 7, 9, 11]
Output: []

Every load in the rig is different, so no two sections can match.

Constraints

The rig holds between 1 and 5000 joints.
1 <= rig.length <= 15000
-200 <= rig[i] <= 200
The first entry of the list is not null.

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 find_duplicate_subtrees(rig: list) -> list[int]:

Java

public int[] findDuplicateSubtrees(Integer[] rig)

The intended approach

Time O(n) over the list's length, the table lookups costing a constant each.Space O(n) for the slots, the table and the tallies.

Read the list level by level first, recording for every joint where its two slots sit and collecting the joints in the order they were read. Since that order runs from the top down, walking it backwards settles every joint after everything below it. Give each section a plain number that stands in for its whole shape and all its loads. Build a key from the joint's load together with the numbers already given to the sections in its two slots, using a stand-in value for an empty slot, and look the key up in a table. A key seen before hands back the number it had; a fresh key takes the next unused number. Two sections end up with the same number exactly when they are alike, because the key pins down the load and both slots, and both slots were already settled. Alongside the table, keep for each number the earliest position it was handed to and how many times it came up. Sorting the earliest positions of the numbers that came up more than once gives the answer. Comparing numbers rather than whole sections is what keeps each joint's work constant.

Pythonentry point: find_duplicate_subtrees

def find_duplicate_subtrees(rig):
    n = len(rig)
    if n == 0:
        return []
    left = {}
    right = {}
    order = [0]
    level = [0]
    at = 1
    while level and at < n:
        nxt = []
        for owner in level:
            if at < n:
                if rig[at] is not None:
                    left[owner] = at
                    nxt.append(at)
                at += 1
            if at < n:
                if rig[at] is not None:
                    right[owner] = at
                    nxt.append(at)
                at += 1
        order.extend(nxt)
        level = nxt
    marks = {}
    kind = {}
    tally = {}
    first = {}
    for pos in reversed(order):
        key = (rig[pos],
               kind.get(left.get(pos), -1),
               kind.get(right.get(pos), -1))
        if key in marks:
            mark = marks[key]
        else:
            mark = len(marks)
            marks[key] = mark
        kind[pos] = mark
        tally[mark] = tally.get(mark, 0) + 1
        if mark not in first or pos < first[mark]:
            first[mark] = pos
    return sorted(first[mark] for mark in tally if tally[mark] > 1)

The obvious version

Spell every section out in full instead. A section's spelling is its joint's load followed by the spellings of its two slots, with a marker standing for an empty slot, all wrapped in brackets so the pieces cannot run together. Sections are alike exactly when their spellings match, so gather the positions by spelling and keep the earliest of every group holding more than one. Costs the length of the spellings, which grows with the rig, rather than a constant per section.

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_find_duplicate_subtrees(rig):
    n = len(rig)
    if n == 0:
        return []
    left = {}
    right = {}
    level = [0]
    at = 1
    while level and at < n:
        nxt = []
        for owner in level:
            if at < n:
                if rig[at] is not None:
                    left[owner] = at
                    nxt.append(at)
                at += 1
            if at < n:
                if rig[at] is not None:
                    right[owner] = at
                    nxt.append(at)
                at += 1
        level = nxt
    groups = {}
    def spell(pos):
        if pos is None:
            return "#"
        text = "(" + str(rig[pos]) + spell(left.get(pos)) + spell(right.get(pos)) + ")"
        groups.setdefault(text, []).append(pos)
        return text
    spell(0)
    out = []
    for _text, spots in groups.items():
        if len(spots) > 1:
            out.append(min(spots))
    return sorted(out)

How this problem was checked

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