0389EasyLinked ListRecursion

Unlink Matching Bins

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.

Parts bins travel down a line hooked together in a single chain, each bin holding a hook to the one behind it. The chain is given to you as chain, the list of bin labels from the front hook to the last bin; an empty list means the line is running empty.

Every bin whose label equals target has to come off the line. Take each one out by re-hooking its predecessor to its successor, so the bins that stay keep their order and the rest of the chain is untouched.

Return the labels of the chain that is left, again from front to back, or an empty list if no bin survives. Solve it by walking the chain and moving hooks, not by filtering the list with a library call, and remember that the very first bin may also have to come off.

Examples

Example 1

Input: chain = [1, 7, 7, 2], target = 7
Output: [1, 2]

Both middle bins carry label 7, so bin 1 is re-hooked straight to bin 2.

Example 2

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

The two bins at the front both come off, and the front hook moves to bin 3.

Example 3

Input: chain = [1, 2, 3], target = 9
Output: [1, 2, 3]

No bin carries label 9, so the chain comes back unchanged.

Example 4

Input: chain = [4, 4, 4], target = 4
Output: []

Every bin matches, so the line ends up empty.

Constraints

0 <= chain.length <= 10^4
1 <= chain[i] <= 50
0 <= target <= 50

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 remove_elements(chain: list[int], target: int) -> list[int]:

Java

public int[] removeElements(int[] chain, int target)

The intended approach

Time O(n)Space O(n) for the bins and the returned labels

Wire the labels into bins that each hold a hook to the next one, then put an extra gate node in front of the head so the head is not a special case. Walk the chain holding the last kept bin: when the current bin matches, re-hook the kept bin past it, otherwise the current bin becomes the last kept one. Reading the hooks from the gate afterwards gives the surviving labels in order.

Pythonentry point: remove_elements

def remove_elements(chain, target):
    # Time O(n) -- one pass to wire the bins up, one to relink, one to read the result.
    # Space O(n) for the bins and the returned labels.
    bins = [[label, None] for label in chain]
    for i in range(len(bins) - 1):
        bins[i][1] = i + 1
    gate = [None, 0 if bins else None]
    prev = gate
    cursor = gate[1]
    while cursor is not None:
        node = bins[cursor]
        nxt = node[1]
        if node[0] == target:
            prev[1] = nxt
        else:
            prev = node
        cursor = nxt
    out = []
    cursor = gate[1]
    while cursor is not None:
        out.append(bins[cursor][0])
        cursor = bins[cursor][1]
    return out

The obvious version

Look up the first matching label and rebuild the list without that position, repeating until no match is left. Quadratic and does no hook bookkeeping.

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_remove_elements(chain, target):
    out = list(chain)
    while target in out:
        cut = out.index(target)
        out = out[:cut] + out[cut + 1:]
    return out

How this problem was checked

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