Find All Duplicates in an Array

Explanation & Solution

Description

Given an integer array nums of length n where all integers are in the range [1, n] and each integer appears once or twice, return an array of all integers that appear twice.

You must write an algorithm that runs in O(n) time and uses only O(1) extra space.

Input:nums = [4, 3, 2, 7, 8, 2, 3, 1]

Output:[3, 2]

Explanation: 3 and 2 each appear twice.

Constraints

n == nums.length
1 <= n <= 10^5
1 <= nums[i] <= n
Each element appears once or twice

Approach

Cyclic Sort pattern

1. Phase 1 — Cyclic Sort

For each index i, compute j = nums[i] - 1 (the correct index for that value)
If nums[i] !== nums[j], swap — the value is misplaced
If nums[i] === nums[j], either the value is already correct or a duplicate exists at index j
In both cases, advance i

2. Why Equality Means Duplicate or Correct

If j === i, then nums[i] = nums[j] trivially — value is in the right place
If j !== i but nums[i] = nums[j], both positions hold the same number — that's a duplicate
Swapping duplicates endlessly would cause an infinite loop, so we advance instead

3. Phase 2 — Collect Duplicates

After the sort, scan every index k
If nums[k] !== k + 1, index k should hold k + 1 but holds the duplicate value nums[k] instead
Collect nums[k] as a duplicate

🧠 Key Insight

After cyclic sort, each position that holds the wrong value reveals a duplicate: the value at nums[k] appears twice (once at nums[k]-1 where it belongs, and once again at k)

Time

O(n)at most n swaps total in Phase 1

Space

O(1) auxiliary (output array excluded)

Visualization

Input:

[4, 3, 2, 7, 8, 2, 3, 1]

—

Press ▶ or use ← → to step through

Pointer iPointer jProcessedDone

19 steps

Solution Code

Find All Numbers Disappeared in an Array

Set Mismatch