442. Find All Duplicates in an Array (Medium)

sorting

• Sort the array and push all the element with frequency 2 in the array.
• Time complexity: O(nlogn)
• Space complexity: O(1)

Code

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums)
    {
        int n = nums.size();
        unordered_map<int, int> mp;
        for (auto x : nums) {
            mp[x]++;
        }
        vector<int> ans;
        for (auto x : mp) {
            if (x.second == 2) {
                ans.push_back(x.first);
            }
        }
        return ans;
    }
};

Map Solution

• Store the frequency of all the elements in the map.
• return vector of all the elements with frequency 2 as answer.

Code

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums)
    {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<int> ans;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] == nums[i + 1])
                ans.push_back(nums[i]);
        }
        return ans;
    }
};