0185MediumLinked List

Flip a Span of the Gauge 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 pipeline is instrumented with gauges wired in a single direction: every gauge holds one signed drift reading and points at the gauge downstream of it, and the final gauge points at nothing.

The harness only carries plain JSON, so the chain reaches you as the array drifts, listing the readings from the first gauge through to the last. Your answer takes the same shape: the readings of the rewired chain, first gauge first.

Gauges are numbered from 1. Turn the run of gauges from position left through position right around, so the gauge that was last in that run now comes first and the gauge that was first in it now comes last. Everything outside the run keeps its place, and the run stays joined to whatever sat on either side of it.

Do this by rewiring, not by copying readings into a fresh chain: rebuild the gauges from the array, redirect the wires, and beyond those gauges and the array you hand back hold only a fixed number of gauge references. Walk the chain once.

Examples

Example 1

Input: drifts = [12, -4, 0, 7, 9, -1], left = 2, right = 5
Output: [12, 9, 7, 0, -4, -1]

Gauges at positions 2 through 5 carry -4, 0, 7 and 9; after rewiring that run reads 9, 7, 0, -4, while the gauges at positions 1 and 6 stay put.

Example 2

Input: drifts = [-8, 3], left = 1, right = 2
Output: [3, -8]

The run covers the whole chain, so the two gauges trade places.

Example 3

Input: drifts = [5, 5, -2, 5], left = 3, right = 3
Output: [5, 5, -2, 5]

A run of one gauge has nothing to turn around, so the chain is handed back unchanged.

Constraints

The chain holds n gauges
1 <= n <= 500
-500 <= drifts[i] <= 500
1 <= left <= right <= n
Beyond the rebuilt gauges and the array you return, only a fixed number of gauge references may be held

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 flip_chain_span(drifts: list[int], left: int, right: int) -> list[int]:

Java

public int[] flipChainSpan(int[] drifts, int left, int right)

The intended approach

Time O(n)Space O(n) for the gauges rebuilt from the input and the returned array, plus O(1) gauge references beyond them

Rebuild the gauges, then park an extra anchor gauge ahead of the head so a run starting at position 1 needs no special case. Step to the gauge just before the run, keep a reference to the run's original first gauge as its future tail, and repeatedly unhook the gauge after that tail and splice it directly behind the anchor point. After right minus left splices the run is turned around and still joined at both ends, so one walk of the chain collects the answer.

Pythonentry point: flip_chain_span

def flip_chain_span(drifts, left, right):
    # Rebuild the chain, then splice each gauge of the run to the front of the
    # run in turn, which reverses it while walking the chain a single time.
    # Time O(n). Space is O(n) for the rebuilt gauges and the returned array,
    # with only a fixed number of gauge references held beyond them.
    class Gauge(object):
        __slots__ = ("drift", "nxt")

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

    head = None
    tail = None
    for drift in drifts:
        gauge = Gauge(drift)
        if head is None:
            head = gauge
        else:
            tail.nxt = gauge
        tail = gauge

    anchor = Gauge(0)
    anchor.nxt = head
    before = anchor
    for _ in range(left - 1):
        before = before.nxt
    run_tail = before.nxt
    mover = run_tail.nxt
    for _ in range(right - left):
        run_tail.nxt = mover.nxt
        mover.nxt = before.nxt
        before.nxt = mover
        mover = run_tail.nxt

    out = []
    node = anchor.nxt
    while node is not None:
        out.append(node.drift)
        node = node.nxt
    return out

The obvious version

Ignore the wiring entirely and work on a copy of the array by index, trading the outermost pair of the run and closing in until the two cursors meet.

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_flip_span(drifts, left, right):
    out = list(drifts)
    lo = left - 1
    hi = right - 1
    while lo < hi:
        out[lo], out[hi] = out[hi], out[lo]
        lo += 1
        hi -= 1
    return out

How this problem was checked

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