1105EasyTreeDepth-First SearchBreadth-First SearchBinary Tree

Do Two Lamps Hang as Cousins

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 frame hangs from a single top lamp. Every lamp holds at most two lamps below it in a first and a second slot, and either slot may be empty. Every lamp carries a different label.

A flat list is read level by level: its first entry is the top lamp's label, 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.

Two lamps are cousins when they hang the same number of slots below the top lamp and they do not hang from the same lamp.

The labels x and y are different and both appear in the frame. Return true when the lamps carrying them are cousins.

Examples

Example 1

Input: frame = [1, 2, 3, 4, null, null, 5], x = 4, y = 5
Output: true

Both lamps hang two slots below the top. Lamp 4 hangs from lamp 2 and lamp 5 hangs from lamp 3, so they are cousins.

Example 2

Input: frame = [1, 2, 3], x = 2, y = 3
Output: false

The two lamps hang the same distance down, but both of them hang from the top lamp.

Example 3

Input: frame = [1, 2, 3, 4, 5, 6, 7], x = 4, y = 3
Output: false

Lamp 4 hangs two slots down while lamp 3 hangs only one, so the distances differ.

Constraints

2 <= frame.length <= 200
The frame holds between 2 and 100 lamps.
1 <= frame[i] <= 100
no two lamps carry the same label
x != y
both x and y appear in the frame

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 is_cousins(frame: list, x: int, y: int) -> bool:

Java

public boolean isCousins(Integer[] frame, int x, int y)

The intended approach

Time O(n) over the lamps.Space O(n) for the slot links and the two facts per lamp.

Two facts about a lamp settle the question: how many slots below the top it hangs, and which lamp it hangs from. Both fall out of one walk over the frame. Read the flat list into slot links, then step through the lamps in the order they were discovered, which always reaches a lamp before the lamps below it. For each lamp fill in its two slots: their distance down is one more than the lamp's own, and the lamp they hang from is the lamp itself. The top lamp starts at distance zero and hangs from nothing. A lookup from label to lamp then answers the question outright: the two lamps are cousins when their distances match and the lamps they hang from differ. The second half matters on its own, since two lamps in the two slots of a single lamp share a distance without being cousins, and the first half matters too, since two lamps hanging from different lamps may still sit at different distances.

Pythonentry point: is_cousins

def is_cousins(frame, x, y):

    n = len(frame)
    left = {}
    right = {}
    order = [0]
    level = [0]
    at = 1
    while level and at < n:
        nxt = []
        for owner in level:
            if at < n:
                if frame[at] is not None:
                    left[owner] = at
                    nxt.append(at)
                at += 1
            if at < n:
                if frame[at] is not None:
                    right[owner] = at
                    nxt.append(at)
                at += 1
        order.extend(nxt)
        level = nxt

    rung = {0: 0}
    above = {0: -1}
    for pos in order:
        for child in (left.get(pos), right.get(pos)):
            if child is not None:
                rung[child] = rung[pos] + 1
                above[child] = pos
    spot = {}
    for pos in order:
        spot[frame[pos]] = pos
    a = spot[x]
    b = spot[y]
    return rung[a] == rung[b] and above[a] != above[b]

The obvious version

Hunt down each of the two lamps separately, dragging along the whole run of lamps taken to reach it. Two lamps are cousins when the two runs have the same length and the lamp one step from the end differs. Costs a fresh walk of the frame for each label, carrying a copy of the run at every step.

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_is_cousins(frame, x, y):

    n = len(frame)
    left = {}
    right = {}
    order = [0]
    level = [0]
    at = 1
    while level and at < n:
        nxt = []
        for owner in level:
            if at < n:
                if frame[at] is not None:
                    left[owner] = at
                    nxt.append(at)
                at += 1
            if at < n:
                if frame[at] is not None:
                    right[owner] = at
                    nxt.append(at)
                at += 1
        order.extend(nxt)
        level = nxt

    def route(label):
        stack = [(0, (0,))]
        while stack:
            pos, path = stack.pop()
            if frame[pos] == label:
                return path
            for child in (left.get(pos), right.get(pos)):
                if child is not None:
                    stack.append((child, path + (child,)))
        return None

    first = route(x)
    second = route(y)
    if len(first) != len(second):
        return False
    if len(first) < 2:
        return False
    return first[len(first) - 2] != second[len(second) - 2]

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