Find All Duplicates in an Array

Difficulty: Medium · Pattern: Cyclic Sort / Array Math · Concept: General Coding (DSA) — Core Patterns to Drill

The Gap in the Sequence exploited a bounded-range constraint with a closed-form sum. This problem has a similar-looking setup — n integers, each in 1..n — but the sum trick doesn't apply here: some values appear twice instead of one being missing, and you need to identify which ones, not just detect that something's off.

The cyclic-sort-family technique that does work: since every value is in 1..n, value v "belongs" at index v - 1. Walk the array, and at each value v you encounter, go to index |v| - 1 and flip the sign of whatever's stored there. The first time you visit a given index, its value goes from positive to negative. If you ever land on an index that's already negative, that means its corresponding value has been seen once already — you've found a duplicate.

Your task: implement find_duplicates(nums) in $O(n)$ time and $O(1)$ extra space (beyond the output list) — no set, no counting array, and don't mutate the caller's list. Return the duplicates as a sorted list.

Implement it yourself

assert find_duplicates([4, 3, 2, 7, 8, 2, 3, 1]) == [2, 3]
assert find_duplicates([1, 1, 2]) == [1]
assert find_duplicates([1]) == []
assert find_duplicates([1, 2, 3, 4]) == []

Next: Daily Temperatures