0113EasyTreeDepth-First SearchBreadth-First SearchBinary Tree

Chime Hangs True

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 workshop assembles wind chimes. Everything hangs from one top hook, and each hook or arm may carry up to two arms below it, one on its left side and one on its right side. Every arm has a weight stamped on it.

Because the harness passes plain JSON, the chime arrives as the array joints, listed row by row from the top hook downwards. The first entry is the top hook's weight. After that, entries come in pairs: the next two entries give the left-side arm and the right-side arm of the next piece in that same row order. A side with nothing hanging on it is written null, and a null contributes no pair of its own.

A chime is called true when it is its own reflection: swap left for right everywhere below the top hook and you get the identical assembly, with matching weights and matching empty sides.

Return true if the chime is true, and false if it is not.

Examples

Example 1

Input: joints = [4, 7, 7, 2, 9, 9, 2]
Output: true

The two arms under the hook both weigh 7, and their pairs 2 then 9 on one side face 9 then 2 on the other, so every piece meets its reflection.

Example 2

Input: joints = [8, 3, 3, 7]
Output: false

The left arm carries a 7 on its own left side while the right arm carries nothing at all, so the reflection breaks one row below the hook.

Example 3

Input: joints = [6, 2, 2, 5, null, null, 5]
Output: true

The 5 hangs on the outer side of each 2, which is exactly where a reflection puts it.

Constraints

The number of arms in the chime is in the range [1, 1000].
-100 <= joints[i] <= 100
Entries that are not `null` are integers; `null` marks an empty side.

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 chime_hangs_true(joints: list) -> bool:

Java

public boolean chimeHangsTrue(Integer[] joints)

The intended approach

Time O(n)Space O(n)

Rebuild the arms from the row-by-row listing, then walk the two halves under the top hook together in opposite directions: a piece on the left is compared with its counterpart on the right, and their outer sides are paired with each other while their inner sides are paired with each other. Any weight mismatch, or one side empty where the other is not, ends the walk.

Pythonentry point: chime_hangs_true

def chime_hangs_true(joints):
    class Arm:
        __slots__ = ("weight", "left", "right")

        def __init__(self, weight):
            self.weight = weight
            self.left = None
            self.right = None

    if not joints or joints[0] is None:
        return True
    root = Arm(joints[0])
    row = [root]
    at = 0
    i = 1
    while at < len(row) and i < len(joints):
        arm = row[at]
        at += 1
        if i < len(joints):
            v = joints[i]
            i += 1
            if v is not None:
                arm.left = Arm(v)
                row.append(arm.left)
        if i < len(joints):
            v = joints[i]
            i += 1
            if v is not None:
                arm.right = Arm(v)
                row.append(arm.right)

    def reflects(a, b):
        if a is None and b is None:
            return True
        if a is None or b is None:
            return False
        if a.weight != b.weight:
            return False
        return reflects(a.left, b.right) and reflects(a.right, b.left)

    return reflects(root.left, root.right)

The obvious version

Rebuild the chime, construct a fully mirrored copy by swapping every pair of sides, spell both out including empty sides, and compare the two spellings.

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_chime_hangs_true(joints):
    if not joints or joints[0] is None:
        return True
    root = {"w": joints[0], "l": None, "r": None}
    row = [root]
    at = 0
    i = 1
    while at < len(row) and i < len(joints):
        arm = row[at]
        at += 1
        for side in ("l", "r"):
            if i >= len(joints):
                break
            v = joints[i]
            i += 1
            if v is not None:
                arm[side] = {"w": v, "l": None, "r": None}
                row.append(arm[side])

    def flipped(node):
        if node is None:
            return None
        return {"w": node["w"], "l": flipped(node["r"]), "r": flipped(node["l"])}

    def spell(node):
        if node is None:
            return "#"
        return "(" + str(node["w"]) + spell(node["l"]) + spell(node["r"]) + ")"

    return spell(root) == spell(flipped(root))

How this problem was checked

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