Problem description:

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?

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

Output:
[2,3]

Solution:
First of all, we should notice that the number is ranged from 1...n. So if we use the value-1 as the index, it will not out of range. Therefore, we can use the input array to do the checking. When find a number i, flip the number at position i-1 to negative. If the number at position i-1 is already negative, i is the number that occurs twice.

Example:
input array: [1,2,2,3]
round 1: [-1,2,2,3]
round 2: [-1,-2,2,3]
round 3: [-1,2,2,3] –> the 2nd element become positive after flipping, so add it to result
round 4: [-1,2,-2,3]

time complexity: O(n)
space complexity: O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        for(int i = 0; i < nums.size(); i++){
            nums[abs(nums[i])-1] = -nums[abs(nums[i])-1];
            
            if(nums[abs(nums[i])-1] > 0) 
                res.push_back(abs(nums [i]));
        }
        return res;
    }
};

A regular way to do it. Use a set to check if a number showed up.

1
2
3
4
5
6
7
8
9
10
class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        dup = set()
        res = []
        for n in nums:
            if n in dup:
                res.append(n)
            else:
                dup.add(n)
        return res

Then I realized the input numbers are 1 ≤ a[i] ≤ n (n = size of array). Also, the duplicate would only appear twice. 

1
2
3
4
5
6
7
8
9
class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        res = []
        for n in nums:
            if nums[abs(n)-1] < 0:
                res.append(abs(n))
            else:
                nums[abs(n)-1] *= -1
        return res