260. Single Number III - Explanation

Description

You are 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,1,2,3,2,4]

Output: [3,4]

Example 2:

Input: nums = [2,1]

Output: [2,1]

Example 3:

Input: nums = [-50,1,2,3,3,2,1,10]

Output: [-50,10]

Constraints:

2 <= nums.length <= 30,000
(-(2^31)) <= nums[i] <= ((2^31)-1)
Each integer in nums will appear twice, only two integers will appear once.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

The most straightforward approach is to check each element against every other element. If we find no duplicate for an element, it must be one of the two unique numbers. We collect these unique elements until we find both.

Algorithm

Initialize an empty result list.
For each element at index i, check all other elements at index j.
If no match is found (the element is unique), add it to the result.
Stop once we have found two unique elements.
Return the result.

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        n, res = len(nums), []

        for i in range(n):
            flag = True
            for j in range(n):
                if i != j and nums[i] == nums[j]:
                    flag = False
                    break

            if flag:
                res.append(nums[i])
                if len(res) == 2:
                    break

        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$ extra space.

2. Hash Map

Intuition

We can count occurrences of each number using a hash map. Numbers that appear exactly once are our two unique elements. This trades space for time, reducing the time complexity from quadratic to linear.

Algorithm

Create a hash map to count occurrences of each number.
Iterate through the array and update counts.
Collect all keys with a count of 1 into the result.
Return the result containing the two unique numbers.

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        count = {}
        for num in nums:
            count[num] = 1 + count.get(num, 0)

        return [k for k in count if count[k] == 1]

Time & Space Complexity

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

3. Hash Set

Intuition

A hash set can track numbers we have seen. When we encounter a number for the first time, we add it. When we see it again, we remove it. After processing all numbers, only the two unique elements remain in the set.

Algorithm

Initialize an empty hash set.
For each number in the array:
- If the number is already in the set, remove it.
- Otherwise, add it to the set.
Convert the set to a list and return it.

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        seen = set()
        for num in nums:
            if num in seen:
                seen.remove(num)
            else:
                seen.add(num)
        return list(seen)

Time & Space Complexity

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

4. Sorting

Intuition

Sorting the array groups duplicate numbers together. After sorting, each element should equal either its left or right neighbor if it has a duplicate. Elements that differ from both neighbors are the unique numbers we seek.

Algorithm

Sort the array.
Iterate through each index i.
If nums[i] differs from both nums[i-1] (if exists) and nums[i+1] (if exists), it is unique.
Collect all unique elements and return them.

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        res, n = [], len(nums)
        nums.sort()

        for i in range(n):
            if ((i > 0 and nums[i] == nums[i - 1]) or
                (i + 1 < n and nums[i] == nums[i + 1])):
                continue
            res.append(nums[i])

        return res

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

5. Bitwise XOR (Least Significant Bit)

Intuition

XORing all numbers gives us a ^ b where a and b are the two unique numbers. Since a != b, at least one bit in the XOR result is set. This bit position represents where a and b differ. We can use this differing bit to partition all numbers into two groups: one containing a and one containing b. XORing within each group isolates the unique numbers.

Algorithm

XOR all numbers to get a ^ b.
Find any set bit in the result by iterating until we find a bit position where the XOR is 1.
Partition numbers: those with this bit set go to one group, others to another.
XOR within each group to isolate a and b.
Return both unique numbers.

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        xor = 0
        for num in nums:
            xor ^= num

        diff_bit = 1
        while not (xor & diff_bit):
            diff_bit <<= 1

        a = b = 0
        for num in nums:
            if diff_bit & num:
                a ^= num
            else:
                b ^= num
        return [a, b]

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

6. Bitwise XOR (Most Significant Bit)

Intuition

This approach is similar to the previous one but uses a neat trick to find the rightmost set bit. The expression x & (-x) isolates the lowest set bit in x. Using this on the XOR of all numbers immediately gives us a differing bit between the two unique numbers without looping.

Algorithm

XOR all numbers to get a ^ b.
Compute diff_bit = xor & (-xor) to get the rightmost set bit.
Partition numbers based on whether they have this bit set.
XOR within each partition to find a and b.
Return both unique numbers.

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        xor = 0
        for num in nums:
            xor ^= num

        diff_bit = xor & (-xor)

        a = b = 0
        for num in nums:
            if diff_bit & num:
                a ^= num
            else:
                b ^= num
        return [a, b]

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

Common Pitfalls

Confusing This Problem with Single Number I

Unlike the classic Single Number problem where XORing all elements directly yields the answer, this problem has two unique numbers. XORing all elements gives a ^ b, not the individual values. Candidates often fail to recognize that an additional step is needed to separate the two numbers.

Misunderstanding the Differing Bit Logic

The key insight is that a ^ b has at least one set bit where a and b differ. Using this bit to partition the array into two groups is crucial. A common mistake is not understanding why this partitioning works or incorrectly identifying which bit to use for separation.

Integer Overflow When Finding the Rightmost Set Bit

The expression x & (-x) to find the rightmost set bit can cause overflow issues in some languages when dealing with the minimum integer value. In languages like C++ or Java, negating INT_MIN causes undefined behavior or overflow, requiring careful handling with unsigned types or alternative approaches.