• Posts

Problem 260 Single Number III

Problem Statement

Link - Problem 260

Question

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

Example 1:

Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation:  [5, 3] is also a valid answer.

Example 2:

Input: nums = [-1,0]
Output: [-1,0]

Example 3:

Input: nums = [0,1]
Output: [1,0]

Constraints:

• 2 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 - 1
• Each integer in nums will appear twice, only two integers will appear once.

Solution

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        unordered_map<int, int> frequencyMap;


        for (int num : nums) {
            frequencyMap[num]++;
        }


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

        return result;
    }
};

Complexity Analysis

| Algorithm  | Time Complexity | Space Complexity |
| ---------- | --------------- | ---------------- |
| Hash Table | O(n)            | O(n)             |

Explanation

Intial Thoughts

To solve this problem, we can start by thinking about how to identify the two unique numbers in the array. One approach is to use a frequency map, where we count the occurrences of each number. We can also think about using bitwise operations to find the unique numbers. Another idea is to use a divide-and-conquer approach, where we split the array into smaller sub-arrays and find the unique numbers in each sub-array. Additionally, we need to consider the constraints of linear runtime complexity and constant extra space.

Intuitive Analysis

An intuitive solution involves using a XOR operation, where we XOR all the numbers in the array. The result will be the XOR of the two unique numbers. We can then find the rightmost set bit in the result, which will help us to divide the numbers into two groups. By XORing the numbers in each group separately, we can find the two unique numbers. This approach works because XOR of all elements gives us the XOR of the two unique elements. Another way to look at it is to think of the XOR operation as a way to ‘cancel out’ the numbers that appear twice, leaving us with the two unique numbers.

1. Intuition

• The problem requires finding two elements that appear only once in an array where all other elements appear twice, suggesting a frequency-based approach
• A hash map can be used to store the frequency of each element, allowing for efficient lookup and counting
• The problem constraints specify linear runtime complexity and constant extra space, but the given solution uses extra space, indicating a potential issue
• The key insight is to recognize that the XOR operation can be used to find the two single numbers, as XOR of all elements will give the XOR of the two single numbers
• However, the given solution uses an unordered map, which does not meet the constant extra space requirement
• A more efficient solution would involve using bitwise operations to find the single numbers, meeting the space and time complexity requirements
• The XOR operation has the property that a ^ a = 0 and a ^ 0 = a, which can be utilized to find the single numbers

2. Implementation

• The given solution uses an unordered_map called frequencyMap to store the frequency of each element in the nums array
• It iterates over the nums array, incrementing the count for each element in the frequencyMap using frequencyMap[num]++
• It then iterates over the frequencyMap and adds elements with a count of 1 to the result vector using result.push_back(entry.first)
• However, a more efficient implementation would involve using bitwise operations, such as XOR, to find the single numbers
• This can be achieved by using the ^ operator to XOR all elements in the nums array, giving the XOR of the two single numbers
• The result can be obtained by using bitwise operations to separate the two single numbers from the XOR result
• The implementation would involve using int xorResult = 0; and xorResult ^= num; to calculate the XOR of all elements

Complexity Analysis

Time Complexity:

• The algorithm starts by iterating over the input array nums using a for loop, which results in a time complexity of O(n) for this step. This is because the loop iterates over each element once, where n is the number of elements in nums. The frequencyMap operations (frequencyMap[num]++) within the loop also take constant time, thus not affecting the overall time complexity.
• The second loop iterates over the frequencyMap using a range-based for loop, which also has a time complexity of O(n) in the worst case. However, since the size of frequencyMap is at most n (when all numbers are unique), this operation does not change the overall time complexity.
• Considering both loops, the overall time complexity remains O(n) + O(n) = O(2n), which simplifies to O(n) because constant factors are ignored in Big O notation.

Space Complexity:

• The algorithm uses an unordered_map called frequencyMap to store the frequency of each number in the input array nums. In the worst-case scenario, where all numbers are unique, the size of frequencyMap will be equal to the size of nums, i.e., n.
• Additionally, a result vector is used to store the numbers that appear only once. In the worst-case scenario (when all numbers are unique except two), the size of result will be 2.
• Therefore, the overall space complexity is O(n) due to the frequencyMap, which dominates the space usage, and the result vector’s space usage is relatively constant, thus not affecting the overall space complexity.

Footnote

This question is rated as Medium difficulty.

Similar Questions: