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, with each value present either once or twice. Return an array holding every value that shows up twice.

Example

Input: nums = [5,1,5,3,3,2,6,6]
Output: [3,5,6]
Explanation: 3, 5 and 6 each appear twice; 1 and 2 appear once.

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 index (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 target index = |value| - 1
  2. If nums[index] is negative, value is a duplicate
  3. Otherwise, mark nums[index] as negative

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

Pseudocode

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

Hints

  • Values are in range [1, n], use values as indices!
  • Mark visited by making the value at that index 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 index (x-1), allowing us to use indices 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