Find All Duplicates in an Array Solution

Problem

Given an array of integers where every value is between 1 and n (inclusive) and each integer appears exactly once or twice, find all the values that appear twice. You must solve this in O(n) time using only constant extra space.

Input: nums = [4, 3, 2, 7, 8, 2, 3, 1]
Output: [2, 3]
Explanation: 2 and 3 each appear exactly twice; all other values appear once.

Intuition

Because every value is in the range [1, n], each value can serve as a pointer to an index in the same array. Visiting index abs(value) - 1 and negating what's there acts as a "visited" marker — if you arrive at an index that's already negative, you've seen this value before, meaning it's a duplicate.

Approach 1 — Hash Set

Scan the array once, adding each value to a set. If a value is already in the set, it's a duplicate.

Initialize an empty hash set and an empty result list.
For each number in the array, check if it's already in the set.
If yes, add it to the result list.
If no, add it to the set and continue.
Return the result list.

1def findDuplicates(nums: list[int]) -> list[int]:
2    seen = set()
3    result = []
4    for num in nums:
5        if num in seen:
6            result.append(num)
7        else:
8            seen.add(num)
9    return result

Time: O(n) — single pass over the array.
Space: O(n) — the hash set can hold up to n/2 entries in the worst case.

Approach 2 — In-Place Index Marking

Use the array itself as the visited marker by negating nums[abs(value) - 1]. An already-negative entry signals a duplicate.

Initialize an empty result list.
For each number in the array, compute index = abs(num) - 1 (values are 1-indexed).
If nums[index] is already negative, abs(num) has been seen before — add it to results.
Otherwise, negate nums[index] to mark this value as visited.
Return the result list.

1def findDuplicates(nums: list[int]) -> list[int]:
2    result = []
3    for num in nums:
4        index = abs(num) - 1          # map value to its corresponding index
5        if nums[index] < 0:           # already negated means we've seen this value
6            result.append(abs(num))
7        else:
8            nums[index] = -nums[index]  # mark visited by flipping the sign
9    return result

Time: O(n) — single pass, with O(1) work per element.
Space: O(1) — the input array is modified in place; the output list is not counted as extra space.

Complexity Summary

Approach	Time	Space	When to use
Hash Set	O(n)	O(n)	When you cannot modify the input array
In-Place Index Marking	O(n)	O(1)	When mutation of the input is allowed and space matters

Common Mistakes

Forgetting to take the absolute value before computing the index — by the time you process later elements, some entries may already be negative from earlier markings, so you must use abs(num) - 1, not num - 1.
Off-by-one between values and indices — values run from 1 to n but arrays are 0-indexed, so the index for value v is v - 1, not v.
Checking the sign of num instead of nums[index] — the current element's sign tells you whether it has already been used as an index, not whether its own value is a duplicate; always check nums[index].
Using Approach 2 when the problem forbids mutation — this technique writes to the input; if the caller expects the array unchanged after the call, use the hash set approach instead.
Appending num instead of abs(num) to results — once a value has been negated and then encountered again, num itself is negative; always record abs(num) so the output contains the original positive value.

Find All Duplicates in an Array — Solution