Find All Duplicates in an Array

Problem Overview

Given an array of n integers where every value is between 1 and n and each value appears once or twice, return every value that appears twice, using only O(1) extra space beyond the output.

Why solve this?

The value-range constraint (every element is a valid 1-based index into the same array) is what unlocks an O(1)-extra-space trick: the array can mark which values it has already seen by negating the value stored at the index that value maps to.

Pattern Recognition

Whenever every value in an array is guaranteed to fall within [1, n] for an array of length n, consider using the array itself as a hash set by negating the value at the index each element points to, instead of allocating a separate hash set.

Prerequisites

• Missing Number — the same 'array values as indices' insight, used here to detect a second visit instead of finding an absent one.

Hints

1. Since every value is between 1 and n, each value can be mapped to an index: abs(value) - 1.
2. Visiting a value's index and finding it already negative means that value has been seen before — record it as a duplicate.
3. Otherwise, negate the value stored at that index to mark the value as seen, using the array itself as the 'seen' hash set.

Approach

Because every value is guaranteed to be in [1, n] for an array of length n, each value can be treated as a pointer to one of the array's own indices: value v maps to index v - 1. Scan the array once; for each element, compute index = abs(nums[i]) - 1 (abs is needed because a value may already have been negated by an earlier step). If nums[index] is already negative, that value has been visited before — it's a duplicate, so record abs(nums[i]) in the result. Otherwise, negate nums[index] to mark that value as now seen, and move on. This uses the array itself as an implicit hash set instead of allocating a separate one, which is what achieves O(1) extra space — but it does mean the input array's contents are changed during the scan (some values end up negated), which is worth stating plainly rather than leaving implicit.

Code

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int index = Math.abs(nums[i]) - 1;
            if (nums[index] < 0) {
                result.add(Math.abs(nums[i]));
            } else {
                nums[index] = -nums[index];
            }
        }
        return result;
    }
}

Related Problems

• Reverse an Arrayeasy
• Second Largest Element in an Arrayeasy
• Plus Oneeasy
• Running Sum of 1d Arrayeasy