Find All Duplicates in an Array

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example: Input: [4,3,2,7,8,2,3,1]

Output: [2,3]

Solution: Without extra space

The idea is to use the input array to store the appearance of each elements. But unlike finding all missing numbers, we need to check if element appears twice while looping.

vector<int> findDuplicates(vector<int>& nums) {
    vector<int> result;
    for(int i=0; i<nums.size(); i++) {
        int index = abs(nums[i]) - 1;
        if(nums[index] < 0) {
            result.push_back(index+1);
        }
        nums[index] = -1 * nums[index];
    }        
    return result;
}

results matching ""

    No results matching ""