0299MediumLinked ListTwo Pointers

Unique Scan Trim

Tracked in this browser only

Trains the technique from

LeetCode 82Remove Duplicates from Sorted List II

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 turnstile writes each badge it reads into a chain of records, one record per read, ordered so the badge numbers never decrease from the front of the chain to the back. The chain is handed to you as scans, the badge number of every record in front-to-back order, and an empty chain arrives as an empty list.

A badge that was read more than once is treated as unusable, so every record carrying that badge number leaves the chain, not just the repeats. Records whose badge number appears exactly once stay where they are.

Return the badge numbers of the records still in the chain, front to back. Do the work by unlinking records from the chain as you walk it once, rather than by tallying the whole chain into a fresh structure first.

Examples

Example 1

Input: scans = [-3,-3,-1,0,0,0,4]
Output: [-1,4]

Badge -3 was read twice and badge 0 three times, so all of those records leave. Badges -1 and 4 were read once each and keep their front-to-back order.

Example 2

Input: scans = [7,7,7,8,9,9]
Output: [8]

Badge 7 appears three times and badge 9 twice, so only the single record for badge 8 remains.

Constraints

The number of records in the chain is in the range [0, 300].
-100 <= badge number <= 100
Badge numbers never decrease from the front of the chain to the back.

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 keep_singletons(scans: list[int]) -> list[int]:

Java

public int[] keepSingletons(int[] scans)

The intended approach

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

Because equal badge numbers are already neighbours, one forward walk is enough. At each position, advance a second index to the end of the run of equal values, keep the value only when that run turned out to be a single record, and resume the walk at the first position after the run.

Pythonentry point: keep_singletons

def keep_singletons(scans):
    # One walk from front to back.  Each stop measures how long the run of equal
    # values is and then jumps the whole run, linking the value in behind the last
    # kept node only when that run turned out to hold a single node.
    # O(n) time, O(1) space beyond the returned chain.
    kept = []
    i = 0
    n = len(scans)
    while i < n:
        j = i + 1
        while j < n and scans[j] == scans[i]:
            j += 1
        if j - i == 1:
            kept.append(scans[i])
        i = j
    return kept

The obvious version

Tally how often each badge number occurs in a dictionary, then keep the records whose tally is exactly one.

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_keep_singletons(scans):
    tally = {}
    for v in scans:
        tally[v] = tally.get(v, 0) + 1
    return [v for v in scans if tally[v] == 1]

How this problem was checked

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