0316MediumLinked ListTwo Pointers

Drop the Middle Pallet

Tracked in this browser only

Trains the technique from

LeetCode 2095Delete the Middle Node of a Linked List

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.

Pallets on a tow line are coupled nose to tail, each one hitched to the next. The line is handed to you as chain, the list of pallet tags read from the front of the line to the back, so chain[0] is the leading pallet.

Uncouple the middle pallet and close the gap by hitching its predecessor straight to its successor. Numbering the pallets 0, 1, 2, ... from the front, the middle pallet is the one at position floor(n / 2), where n is how many pallets are on the line. A line of one pallet loses that pallet and ends up empty.

Return the tags of the pallets still on the line, front to back. Aim for O(n) time and O(1) extra space beyond the line you return.

Examples

Example 1

Input: chain = [8, 5, 9, 2, 7]
Output: [8, 5, 2, 7]

Five pallets, so the middle one sits at position floor(5 / 2) = 2, which is the pallet tagged 9. Pallet 5 is hitched to pallet 2 in its place.

Example 2

Input: chain = [4, 6, 1, 3, 9, 5]
Output: [4, 6, 1, 9, 5]

Six pallets, so position floor(6 / 2) = 3 goes, which is the pallet tagged 3.

Example 3

Input: chain = [12]
Output: []

One pallet sits at position floor(1 / 2) = 0, so the line ends up empty.

Example 4

Input: chain = [7, 7]
Output: [7]

Two pallets, so position floor(2 / 2) = 1 goes, which is the second of the two identical tags. The remaining pallet keeps its place at the front.

Example 5

Input: chain = [10, 20, 30]
Output: [10, 30]

Three pallets, so position floor(3 / 2) = 1 goes, which is the pallet tagged 20.

Constraints

1 <= chain.length <= 10^5
1 <= chain[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 drop_middle(chain: list[int]) -> list[int]:

Java

public int[] dropMiddle(int[] chain)

The intended approach

Time O(n)Space O(1) beyond the returned line

Run two pointers along the line. The fast pointer starts one link ahead and moves two links per step while the slow pointer moves one, so when the fast pointer can no longer take a full double step the slow pointer is parked immediately in front of the middle pallet. A line of a single pallet is answered directly. The remaining tags are then emitted in order, skipping the uncoupled position.

Pythonentry point: drop_middle

def drop_middle(chain):
    # Two index pointers: the fast one advances two links per step, the slow one
    # advances one, so the slow one lands next to the pallet that must go.
    # O(n) time. O(1) extra space beyond the chain that is returned.
    n = len(chain)
    if n == 1:
        return []
    slow = 0
    fast = 1
    while fast + 2 <= n - 1:
        slow += 1
        fast += 2
    gone = slow + 1
    out = []
    for i in range(n):
        if i != gone:
            out.append(chain[i])
    return out

The obvious version

Measure the line, compute the middle position directly, and paste together the part before it and the part after 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_drop_middle(chain):
    n = len(chain)
    cut = n // 2
    return chain[:cut] + chain[cut + 1:]

How this problem was checked

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