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() ≤ 106
1 ≤ arr[i] ≤ 5 * 106
arr.size() is even
Approach 01:
-
C++
-
Python
#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)\).