0209MediumLinked ListTwo PointersDivide and ConquerSortingMerge Sort

Order the Sounding Chain

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 survey launch drags a sounder across a harbour and punches every reading onto a paper tag. Each tag holds one reading, the deviation in centimetres between the measured bed and the charted bed, and each tag is stapled to the tag punched after it. The final tag is stapled to nothing, so the run of tags can only be read forwards from the first one.

Because the harness passes plain JSON, the run reaches you as the array soundings, listing the readings from the first tag punched through to the last. An empty array means the launch recorded nothing. Your answer comes back in the same shape: the readings of the reordered run, first tag first.

The hydrographer wants the run reordered so the readings climb from lowest to highest. Repeated readings all stay in the run, once for each tag that carries them.

Do the work the tags call for: hold the readings in stapled tags and put them in order by restapling, that is by changing which tag each tag points at. Do not tip the readings into an array and hand that to a library sort. Keep the number of comparisons within O(n log n), and beyond the tags themselves use only a fixed amount of extra room.

Examples

Example 1

Input: soundings = [9, -4, 12, -4, 0, 7]
Output: [-4, -4, 0, 7, 9, 12]

Every reading from the run appears once, and each is at least as large as the one before it. Both tags reading -4 are still there.

Example 2

Input: soundings = [6, -1]
Output: [-1, 6]

The two tags come back with the lower reading in front.

Example 3

Input: soundings = [-15, 3, -15, -15]
Output: [-15, -15, -15, 3]

The three tags reading -15 all sit ahead of the tag reading 3, and none of them is dropped.

Constraints

The number of tags in the run is in the range [0, 5 * 10^4].
-10^5 <= soundings[i] <= 10^5

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 order_the_sounding_chain(soundings: list[int]) -> list[int]:

Java

public int[] orderTheSoundingChain(int[] soundings)

The intended approach

Time O(n log n)Space O(n) for the rebuilt tags and the returned readings, with only a fixed number of tag references beyond them

Rebuild the run as stapled tags, then merge upwards from runs of width one: on each pass, cut off two consecutive runs of the current width, weave them into one ordered run by repeatedly taking whichever front tag reads lower, and staple the result onto the end of what has already been woven. Doubling the width each pass means log n passes over n tags. A stub tag in front of the run gives every weave somewhere to staple its first tag, so no pass needs a special case for the head.

Pythonentry point: order_the_sounding_chain

def order_the_sounding_chain(soundings):
    # Time: O(n log n) -- log n passes, each touching every tag once.
    # Space: O(n) for the rebuilt tags and the returned array, O(1) references beyond them.
    class Tag:
        __slots__ = ("depth", "nxt")

        def __init__(self, depth):
            self.depth = depth
            self.nxt = None

    head = None
    last = None
    count = 0
    for reading in soundings:
        tag = Tag(reading)
        if head is None:
            head = tag
        else:
            last.nxt = tag
        last = tag
        count += 1
    if count < 2:
        return list(soundings)

    def cut(node, size):
        prev = None
        cur = node
        while cur is not None and size:
            prev = cur
            cur = cur.nxt
            size -= 1
        if prev is not None:
            prev.nxt = None
        return cur

    def weave(a, b, joint):
        cur = joint
        while a is not None and b is not None:
            if a.depth <= b.depth:
                cur.nxt = a
                a = a.nxt
            else:
                cur.nxt = b
                b = b.nxt
            cur = cur.nxt
        cur.nxt = a if a is not None else b
        while cur.nxt is not None:
            cur = cur.nxt
        return cur

    stub = Tag(0)
    stub.nxt = head
    width = 1
    while width < count:
        cur = stub.nxt
        stub.nxt = None
        joint = stub
        while cur is not None:
            left = cur
            right = cut(left, width)
            cur = cut(right, width)
            joint = weave(left, right, joint)
        width += width
    out = []
    node = stub.nxt
    while node is not None:
        out.append(node.depth)
        node = node.nxt
    return out

The obvious version

Copy the readings out and selection sort them: scan the whole unplaced remainder for the lowest reading and swap it into position, O(n^2).

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_order_the_sounding_chain(soundings):
    values = list(soundings)
    n = len(values)
    for i in range(n):
        pick = i
        for j in range(i + 1, n):
            if values[j] < values[pick]:
                pick = j
        values[i], values[pick] = values[pick], values[i]
    return values

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