0573MediumArrayHash TableSorting

Twice-Scanned Bin Labels

Tracked in this browser only

Trains the technique from

LeetCode 442Find All Duplicates in an Array

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 stock take produced nums, the sequence of bin labels a handheld scanner read, one entry per scan. There are n scans in total and every label is between 1 and n. A bin was either scanned once or scanned twice; no bin was scanned three times.

Return the labels of the bins that were scanned twice. The labels may be returned in any order, and each such label appears once in the result.

Do this in time linear in n, and without allocating extra room that grows with n: apart from the list you return, only a constant number of extra values may be held, though you are free to rearrange or overwrite nums itself.

Examples

Example 1

Input: nums = [6, 5, 4, 8, 7, 4, 5, 1]
Output: [4, 5]

Labels 4 and 5 were each read twice, while 6, 8, 7 and 1 were each read once.

Example 2

Input: nums = [1, 1]
Output: [1]

Both scans read bin 1, so it is the only label scanned twice.

Example 3

Input: nums = [2, 1]
Output: []

Each of the two bins was scanned once, so nothing is reported.

Constraints

n == nums.length
1 <= n <= 10^5
1 <= nums[i] <= n
Each label appears in nums once or twice.
The result may be returned in any order.

The values you return may be in any order.

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 find_duplicates(nums: list[int]) -> list[int]:

Java

public List<Integer> findDuplicates(int[] nums)

The intended approach

Time O(n), two passes over the scans.Space O(1) beyond the returned list.

Every label lies in `1..n`, so the slot at index `label - 1` belongs to that label and can be borrowed as a one-bit note by flipping the sign of whatever sits there. Walk the scans, reading each entry as a magnitude in case it has already been marked: if that label's slot is already negative the label has been met before, so record it; otherwise flip the slot's sign. A final pass restores the signs so the caller's data is left readable. No structure proportional to `n` is allocated.

Pythonentry point: find_duplicates

def find_duplicates(nums):
    # O(n) time, O(1) extra space beyond the returned list: the labels are a
    # permutation-like range, so slot label-1 can carry the mark for label itself.
    # A negative sign in that slot means the label has been seen before.
    out = []
    for i in range(len(nums)):
        label = nums[i]
        if label < 0:
            label = -label
        slot = label - 1
        if nums[slot] < 0:
            out.append(label)
        else:
            nums[slot] = -nums[slot]
    for i in range(len(nums)):
        if nums[i] < 0:
            nums[i] = -nums[i]
    return out

The obvious version

Tally how often each label was read using a dictionary, then collect the labels whose tally is two.

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_find_duplicates(nums):
    counts = {}
    for v in nums:
        counts[v] = counts.get(v, 0) + 1
    out = []
    for v in sorted(counts):
        if counts[v] == 2:
            out.append(v)
    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