[LeetCode] 442. 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]

Thought process:

Iterate through the array and maintain a hashset of all elements seen. If an element is in the hashset already, it is a duplicate.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

class Solution { public: vector<int> findDuplicates(vector<int>& nums) { vector< int > duplicates; unordered_set< int > set; for (int num : nums) { if (set.find(num) != set.end()) { duplicates.push_back(num); } else { set.insert(num); } } return duplicates; } };

Time complexity: O(n). Space complexity: O(n).

Follow-up:

We have not yet used the fact that 1 <= a[i] <= n. Since every number is positive, we can use the number to index into the array. Every time we see a number nums[i], we turn nums[nums[i] - 1] into negative. So once we see the number to become negative is already negative, we know that nums[i] is a duplicate.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

class Solution { public: vector<int> findDuplicates(vector<int>& nums) { vector< int > duplicates; for (int i = 0; i < nums.size(); i++) { int abso = abs(nums[i]); if (nums[abso - 1] < 0) { duplicates.push_back(abso); } else { nums[abso - 1] = - nums[abso - 1]; } } return duplicates; } };

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