Unique Number II

Given an array arr[] containing 2*n + 2 positive numbers, out of which 2*n numbers exist in pairs whereas only two number occur exactly once and are distinct. Find the other two numbers. Return the answer in increasing order.

Examples:

Input: arr[] = [1, 2, 3, 2, 1, 4]
Output: [3, 4]
Explanation: 3 and 4 occur exactly once.
Input: arr[] = [2, 1, 3, 2]
Output: [1, 3]
Explanation: 1 and 3 occur exactly once.
Input: arr[] = [2, 1, 3, 3]
Output: [1, 2]
Explanation: 1 and 2 occur exactly once.

Constraints:
2 ≤ arr.size() ≤ 10
1 ≤ arr[i] ≤ 5 * 106
arr.size() is even


Approach 01:

#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

class Solution {
public:
    vector<int> singleNum(const vector<int>& nums) {
        unordered_map<int,int> frequencyMap;
        for (int num : nums) {
            ++frequencyMap[num];
        }

        vector<int> uniqueNumbers;
        for (const auto& entry : frequencyMap) {
            int num = entry.first;
            int freq = entry.second;
            if (freq == 1) {
                uniqueNumbers.push_back(num);
            }
        }

        sort(uniqueNumbers.begin(), uniqueNumbers.end());
        return uniqueNumbers;
    }
};

 

Time Complexity:

  • Building Frequency Map:Iterate through nums once, updating the map in \(O(1)\) average time per operation → \(O(n)\).
  • Collecting Unique Elements:Iterate through the map (at most \(n\) entries) → \(O(n)\).
  • Sorting Result:Sort the unique numbers array of size \(k \le n\), taking \(O(k \log k)\). In the worst case \(k = n\), so \(O(n \log n)\).
  • Total Time Complexity:\(O(n \log n)\).

Space Complexity:

  • Frequency Map:Stores up to \(n\) entries → \(O(n)\).
  • Result Array:Stores up to \(n\) unique numbers → \(O(n)\).
  • Total Space Complexity:\(O(n)\).
import collections
from typing import List

class Solution:
    def singleNum(self, nums: List[int]) -> List[int]:
        frequency = collections.Counter(nums)
        uniqueNumbers = [num for num, count in frequency.items() if count == 1]
        uniqueNumbers.sort()
        return uniqueNumbers

 

Time Complexity:

  • Building Counter:

    Iterate through nums once, updating counts in \(O(1)\) average time per update → \(O(n)\).

  • Filtering Unique Elements:

    Iterate through at most \(n\) map entries → \(O(n)\).

  • Sorting Result:

    Sort the list of unique numbers of length \(k \le n\), which takes \(O(k \log k)\). In the worst case \(k = n\), so \(O(n \log n)\).

  • Total Time Complexity:

    \(O(n \log n)\).

Space Complexity:

  • Counter Storage:

    Stores up to \(n\) counts → \(O(n)\).

  • Result List:

    Stores up to \(n\) unique numbers → \(O(n)\).

  • Total Space Complexity:

    \(O(n)\).

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top