Find All Duplicates in an Array [Medium] — Index as Hash

Problem Statement

Given an integer array nums of length n where all elements are in [1, n], some appear twice and others once. Return all elements that appear twice. O(n) time, O(1) extra space (output list doesn't count).

Input: [4,3,2,7,8,2,3,1] → Output: [2,3]

Intuition

Use the value as an index: for each nums[i], negate nums[abs(nums[i])-1]. If it's already negative, that index+1 is a duplicate.

Solutions

C++

vector<int> findDuplicates(vector<int>& nums) {
    vector<int> res;
    for (int x : nums) {
        int idx = abs(x) - 1;
        if (nums[idx] < 0) res.push_back(idx + 1);
        else nums[idx] = -nums[idx];
    }
    return res;
}

Java

public List<Integer> findDuplicates(int[] nums) {
    List<Integer> res = new ArrayList<>();
    for (int x : nums) {
        int idx = Math.abs(x) - 1;
        if (nums[idx] < 0) res.add(idx + 1);
        else nums[idx] = -nums[idx];
    }
    return res;
}

JavaScript

var findDuplicates = function(nums) {
    const res = [];
    for (let x of nums) {
        const idx = Math.abs(x) - 1;
        if (nums[idx] < 0) res.push(idx + 1);
        else nums[idx] = -nums[idx];
    }
    return res;
};

Python

def findDuplicates(nums: list[int]) -> list[int]:
    res = []
    for x in nums:
        idx = abs(x) - 1
        if nums[idx] < 0:
            res.append(idx + 1)
        else:
            nums[idx] = -nums[idx]
    return res

Complexity

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