Show problems as
Classic problem #82MediumLinked ListTwo Pointers

Remove Duplicates from Sorted List II

Real-world version: Unique Scan Trim
Tracked in this browser only
Read Remove Duplicates from Sorted List II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstRecursion Technique · Linked List, animated step by step

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def keep_singletons(scans: list[int]) -> list[int]:
Java
public int[] keepSingletons(int[] scans)

More on the same topics