Find All Duplicates in an Array

Difficulty: Medium

Problem

A ticket booth hands out numbered tokens from 1 to n, but some tokens were issued twice. You get an integer array nums of length n whose values all lie between 1 and n, and every value that appears appears once or twice (some values may not appear at all). Return an array holding every value that shows up twice, in any order.

Example

Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]
Explanation: 2 and 3 each appear twice; 1, 4, 7 and 8 appear once; 5 and 6 do not appear. Any order is accepted, so [3,2] is also correct.

Brute-force approach

For each element, scan the rest of the array to check if it appears again.

Steps

  1. For each i, check j > i
  2. If nums[i] == nums[j], record nums[i]
  3. Avoid adding the same duplicate multiple times

Time complexity: O(n²) · Space complexity: O(1)

Trade-offs

  • Quadratic time
  • Harder to avoid duplicate reporting without extra logic

Optimal approach

Key insight: Use the array itself as a marker. Value x maps to slot (x-1). First visit marks negative; second visit detects duplicate.

Two approaches: Hash Set (O(n) space) or In-Place Marking (O(1) space).

Steps

  1. For each value, compute its slot = |value| - 1
  2. If nums[slot] is negative, value is a duplicate
  3. Otherwise, mark nums[slot] as negative

Time complexity: O(n) · Space complexity: O(1)

Pseudocode

function findDuplicates(nums):
    result = empty list
    for i from 0 to n-1:
        slot = |nums[i]| - 1
        if nums[slot] < 0:
            add |nums[i]| to result
        else:
            nums[slot] = -nums[slot]
    return result

Hints

  • Values are in range [1, n], so each value can point at a slot of nums!
  • Mark visited by making the value at that slot negative
  • If already negative, we've seen this value before

Complexity questions

Why can we use the array as a marker for this problem?

Because values are in range [1, n]. The constraint that values are in [1, n] means value x can map to slot (x-1), allowing us to use slots as markers.

Time complexity of the in-place marking solution?

O(n). Single pass through the array with O(1) operations per element.

Space complexity of the in-place marking solution?

O(1). No extra data structures needed - we modify the input array itself.

Check your understanding of Find All Duplicates in an Array

What values can nums[i] take in this problem?

Between 1 and n. The problem guarantees values are in the range [1, n].

How many times can a value appear?

Once or twice. Each integer appears once or twice.

Related problems

Keep practising