Show problems as
Classic problem #442MediumArrayHash TableSorting

Find All Duplicates in an Array

Real-world version: Twice-Scanned Bin Labels
Tracked in this browser only
Read Find All Duplicates in an Array on LeetCode(opens in a new tab)

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

Learn the pattern firstPrefix Sums · Arrays, animated step by step

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

Python
def find_duplicates(nums: list[int]) -> list[int]:
Java
public List<Integer> findDuplicates(int[] nums)

More on the same topics