0114EasyLinked ListTwo PointersStackRecursion

Stamp Chain Echo

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 packing line stamps one digit on every parcel and clips the parcels into a single chain: each parcel holds its digit plus a clip fastened to the parcel behind it, and the parcel at the end has an empty clip.

Because the harness passes plain JSON, the chain reaches you as the array stamps, listing the digits in clip order starting at the front parcel. There is always at least one parcel.

The line supervisor calls a chain an echo when the digits spell out the same run walked from the front as they do walked from the end.

Return true when the chain is an echo, false otherwise. Work with the clips rather than around them: rebuild the parcels, locate the halfway parcel by moving one cursor forward one parcel at a time and a second cursor two at a time, refasten the clips of the leading half backwards as that cursor passes them, then step outwards from the middle comparing digits. Apart from the parcels themselves, hold only a fixed number of parcel references: no second array, no copied string, no growing stack.

Examples

Example 1

Input: stamps = [7, 4, 4, 7]
Output: true

Walking from either end gives 7, 4, 4, 7, so the chain is an echo.

Example 2

Input: stamps = [9, 3, 5]
Output: false

The front parcel is stamped 9 while the end parcel is stamped 5, so the two walks part company immediately.

Example 3

Input: stamps = [2, 8, 2]
Output: true

The outer parcels agree and the single middle parcel has no partner to match, so the chain is an echo.

Constraints

The number of parcels in the chain is in the range [1, 10^5].
0 <= stamps[i] <= 9

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 stamp_chain_echo(stamps: list[int]) -> bool:

Java

public boolean stampChainEcho(int[] stamps)

The intended approach

Time O(n)Space O(n) for the parcels built from the array, plus O(1) parcel references beyond them

Materialise the parcels, then make one pass with a slow cursor and a fast cursor. The fast cursor covers two clips per step so it reaches the end as the slow cursor reaches the middle, and each time the slow cursor moves it refastens its clip to the parcel it just left, leaving the leading half running backwards from the middle. An odd count means the slow cursor sits on the unpaired middle parcel, so skip it. Then walk the two half-chains outward together, comparing digits.

Pythonentry point: stamp_chain_echo

def stamp_chain_echo(stamps):
    class Parcel:
        __slots__ = ("digit", "clip")

        def __init__(self, digit):
            self.digit = digit
            self.clip = None

    head = None
    tail = None
    for digit in stamps:
        parcel = Parcel(digit)
        if head is None:
            head = parcel
        else:
            tail.clip = parcel
        tail = parcel
    if head is None or head.clip is None:
        return True
    behind = None
    slow = head
    fast = head
    while fast is not None and fast.clip is not None:
        fast = fast.clip.clip
        ahead = slow.clip
        slow.clip = behind
        behind = slow
        slow = ahead
    if fast is not None:
        slow = slow.clip
    front = behind
    back = slow
    while front is not None and back is not None:
        if front.digit != back.digit:
            return False
        front = front.clip
        back = back.clip
    return True

The obvious version

Push every digit onto a pile, then read the digits front to back while popping the pile, which serves them back to front; any disagreement settles it.

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_stamp_chain_echo(stamps):
    pile = []
    for digit in stamps:
        pile.append(digit)
    for digit in stamps:
        if digit != pile.pop():
            return False
    return True

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