LeetCode 260: Single Number III — Bitmask Partitioning

In our previous decode on LeetCode 136: Single Number, we saw how XOR can cancel out duplicate numbers and leave a single unique integer behind. It was elegant, linear in time $\mathcal{O}(n)$, and required zero extra space $\mathcal{O}(1)$.

But what happens when the constraints shift? What if the array has two unique elements instead of one?

This is LeetCode 260: Single Number III. If we XOR everything together, the duplicates still cancel out, but we are left with the combined XOR sum of our two unique numbers: A ^ B. Since $A \neq B$, this sum is non-zero, but we can't immediately tell who $A$ and $B$ are.

In this guide, we’ll step through the logic of how to crack this problem, transitioning from simple hash tables to sorting, and finally to the optimal bitwise partitioning technique.

The Core Problem

Given a non-empty array of integers nums, exactly two elements appear only once, and all other elements appear exactly twice. Find the two unique elements. You can return the answer in any order.

The Constraints

• Time Complexity: $\mathcal{O}(n)$ — Single scan or constant number of passes.
• Space Complexity: $\mathcal{O}(1)$ — No scaling auxiliary memory.

Read the original LeetCode 260 Problem →

Approach 1: The Intuitive Frequency Map ($\mathcal{O}(n)$ Time, $\mathcal{O}(n)$ Space)

The most direct approach is to store the counts of each number. We iterate through the array, count the frequency of each element in a hash map, and then collect the ones that appeared exactly once.

Python Solution (Frequency Map)

def singleNumber(nums: list[int]) -> list[int]:
    counts = {}
    for num in nums:
        counts[num] = counts.get(num, 0) + 1
        
    return [num for num, count in counts.items() if count == 1]

C++ Solution (Frequency Map)

#include <vector>
#include <unordered_map>
 
std::vector<int> singleNumber(std::vector<int>& nums) {
    std::unordered_map<int, int> counts;
    for (int num : nums) {
        counts[num]++;
    }
    std::vector<int> result;
    for (auto const& [key, val] : counts) {
        if (val == 1) {
            result.push_back(key);
        }
    }
    return result;
}

Java Solution (Frequency Map)

import java.util.HashMap;
import java.util.Map;
import java.util.ArrayList;
import java.util.List;
 
class Solution {
    public int[] singleNumber(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }
        int[] result = new int[2];
        int idx = 0;
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (entry.getValue() == 1) {
                result[idx++] = entry.getKey();
            }
        }
        return result;
    }
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(n)$ — We scan the input array of size $n$ once to populate the frequency map, and then iterate over the map keys.
• Space Complexity: $\mathcal{O}(n)$ — In the worst case, we store roughly $n/2$ unique elements in the map. This fails the constant space constraint.

Approach 2: Sorting and Two-Pointer Scan ($\mathcal{O}(n \log n)$ Time, $\mathcal{O}(1)$ Space)

If we sort the array, identical numbers will sit next to each other. We can then step through the array:

• If nums[i] == nums[i + 1], we skip both (i += 2).
• If nums[i] != nums[i + 1] (or we reach the end of the array), then nums[i] is one of our unique numbers. We record it and move forward by one step (i += 1).

Python Solution (Sorting)

def singleNumber(nums: list[int]) -> list[int]:
    nums.sort()
    result = []
    i = 0
    while i < len(nums):
        if i == len(nums) - 1 or nums[i] != nums[i + 1]:
            result.append(nums[i])
            i += 1
        else:
            i += 2
    return result

C++ Solution (Sorting)

#include <vector>
#include <algorithm>
 
std::vector<int> singleNumber(std::vector<int>& nums) {
    std::sort(nums.begin(), nums.end());
    std::vector<int> result;
    int i = 0;
    int n = nums.size();
    while (i < n) {
        if (i == n - 1 || nums[i] != nums[i + 1]) {
            result.push_back(nums[i]);
            i += 1;
        } else {
            i += 2;
        }
    }
    return result;
}

Java Solution (Sorting)

import java.util.Arrays;
 
class Solution {
    public int[] singleNumber(int[] nums) {
        Arrays.sort(nums);
        int[] result = new int[2];
        int idx = 0;
        int i = 0;
        while (i < nums.length) {
            if (i == nums.length - 1 || nums[i] != nums[i + 1]) {
                result[idx++] = nums[i];
                i += 1;
            } else {
                i += 2;
            }
        }
        return result;
    }
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(n \log n)$ — Driven by the sorting step.
• Space Complexity: $\mathcal{O}(1)$ (ignoring recursion stack space used by quicksort/heapsort implementations, which is typically $\mathcal{O}(\log n)$).

Approach 3: Bitmask Grouping and Partitioning ($\mathcal{O}(n)$ Time, $\mathcal{O}(1)$ Space)

To get linear time and constant space, we build upon the XOR operator.

If we XOR every number in the array, all duplicate elements will cancel out, leaving: $\text{xor\_sum} = A \oplus B$

Where $A$ and $B$ are our two unique numbers. Since $A \neq B$, the value of $\text{xor\_sum}$ must have at least one bit set to 1.

A set bit (1) in $A \oplus B$ means that at that specific bit position, $A$ and $B$ have different values (one has a 0 at that position, and the other has a 1).

We can use this "difference bit" to partition the entire array into two separate groups:

1. Group 1: All numbers that have a 1 at this bit position.
2. Group 2: All numbers that have a 0 at this bit position.

By doing this, we guarantee that:

• $A$ will fall into one group, and $B$ will fall into the other.
• All duplicate pairs will fall into the same group (because identical numbers have identical bits).

If we XOR all the numbers within Group 1, all duplicate pairs in that group cancel out, isolating $A$. If we XOR all the numbers within Group 2, all duplicate pairs in that group cancel out, isolating $B$.

The Mechanics of xor_sum & -xor_sum

How does this trick isolate the rightmost set bit? It relies on how negative numbers are represented in computers: Two's Complement.

To negate a binary number x (i.e., compute -x), the CPU performs two operations:

1. Invert all bits of x (bitwise NOT: ~x).
2. Add 1 to the inverted result (~x + 1).

Let's trace what happens with an example where x = 12 (binary 001100):

1. Original value (x):

   0 0 1 1 0 0

   The rightmost set bit is at position 2 (value 4).

2. Flipped value (~x):

   1 1 0 0 1 1

   All bits to the left of our rightmost set bit are inverted. All bits to the right are inverted to 1s. The set bit itself becomes 0.

3. Negated value (-x = ~x + 1):

     1 1 0 0 1 1
   +           1
   -------------
     1 1 0 1 0 0

   Adding 1 causes a carry-over to ripple through the trailing 1s (converting them back to 0s) until it hits the first 0, turning it into a 1. This is exactly the position of the rightmost set bit in our original number!

4. Bitwise AND (x & -x):

     x:  0 0 1 1 0 0
    -x:  1 1 0 1 0 0
   -----------------
   AND:  0 0 0 1 0 0  (Decimal 4)

   Because all bits to the left of the rightmost set bit are opposite in x and -x, they AND to 0. All trailing bits are 0 in both, so they AND to 0. Only the rightmost set bit is 1 in both, isolating it perfectly.

Low-Level Edge Case: C++ Integer Overflow

In systems languages like C++, negating a signed integer that equals INT_MIN (e.g., -2147483648) causes signed integer overflow, which is undefined behavior. Since our array can contain any integer value, the cumulative XOR sum could result in INT_MIN.

To write robust, production-safe systems code, we cast our XOR sum to unsigned int before performing the two's complement negation (-).

Python Solution (Optimal Bitmask)

def singleNumber(nums: list[int]) -> list[int]:
    # Step 1: Get XOR sum of A and B
    xor_sum = 0
    for num in nums:
        xor_sum ^= num
        
    # Step 2: Isolate the rightmost set bit using Two's Complement.
    # In binary, x & -x clears all set bits except the lowest one.
    diff_bit = xor_sum & -xor_sum
    
    # Step 3: Partition the array and XOR separately
    a, b = 0, 0
    for num in nums:
        if num & diff_bit:
            a ^= num
        else:
            b ^= num
            
    return [a, b]

C++ Solution (Optimal Bitmask)

#include <vector>
 
class Solution {
public:
    std::vector<int> singleNumber(std::vector<int>& nums) {
        // Cast to unsigned to safely handle two's complement on INT_MIN
        unsigned int xorSum = 0;
        for (int num : nums) {
            xorSum ^= num;
        }
        
        // Isolate the lowest set bit using Two's Complement (x & -x).
        // Since xorSum is cast to unsigned, this negation is safe from signed overflow.
        unsigned int diffBit = xorSum & -xorSum;
        
        int a = 0;
        int b = 0;
        for (int num : nums) {
            if (num & diffBit) {
                a ^= num;
            } else {
                b ^= num;
            }
        }
        return {a, b};
    }
};

Java Solution (Optimal Bitmask)

class Solution {
    public int[] singleNumber(int[] nums) {
        int xorSum = 0;
        for (int num : nums) {
            xorSum ^= num;
        }
        
        // Isolate the rightmost set bit using Two's Complement (x & -x).
        // Java handles signed overflow gracefully on & operations.
        int diffBit = xorSum & -xorSum;
        
        int a = 0;
        int b = 0;
        for (int num : nums) {
            if ((num & diffBit) != 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }
        return new int[]{a, b};
    }
}

Summary of Tradeoffs

Bitmask partitioning is a classic example of using fundamental CPU operations to bypass high-level container overhead. The next time you need to find unique elements under strict limitations, divide and conquer at the binary level!