Find All Duplicates In An Array - Leetcode Solution

Problem Statement:

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 1:

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

Output: [2,3]

Solution:

The idea is to mark numbers as visited by negating the value of that index. For example, if we encounter the value 2, we will go to the index 2-1 and negate the value at that index. This will be our tentative visit of number 2. If we encounter the value 2 again, we will go to the index 2-1, see that the value is already negative, and mark that the number 2 has been seen again.

Now let's look at the implementation.

Step 1: Loop over the array, and at each element, mark the value at index (element - 1) as negative.

Step 2: If we encounter a value again, that means we have seen it before and the index (element - 1) will have already been marked negative. We add the value to our result list.

Step 3: Return the result list.

Code:

class Solution { public: 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);
        } else {
            nums[index] = -nums[index];   
        }
    }
    
    return result;
}

};

The time complexity of this solution is O(n) because we are looping over the array only once. The space complexity is O(1) because we are not using any additional space, except for the result list.

1