Single Number III
Last Updated: March 20, 2026
Understanding the Problem
We have an array where every number appears exactly twice, except for two numbers that appear exactly once. Our job is to find those two unique numbers.
If there were only one unique number, this would be the classic Single Number problem (LeetCode 136), where XOR-ing all elements gives the answer directly. But with two unique numbers, a single XOR pass gives us the XOR of both unknowns mashed together. The real challenge is figuring out how to separate those two numbers from each other.
The problem explicitly asks for O(n) time and O(1) space, which rules out hash maps and sorting. That constraint is a strong hint that bit manipulation is the intended path.
Key Constraints:
2 <= nums.length <= 3 * 10^4→ With n up to 30,000, even O(n^2) would run fine. But the problem explicitly demands O(n) time.-2^31 <= nums[i] <= 2^31 - 1→ Full 32-bit integer range. We need to handle negative numbers, which matters for bit operations.- Exactly two unique elements → This is the structural guarantee we can exploit.
Approach 1: Hash Map
Intuition
The most natural first instinct is to count how many times each number appears, then pick out the ones that show up only once. A hash map is perfect for this since it gives us O(1) lookups and insertions.
We scan through the array, building a frequency count for every number. Then we make a second pass over the map to collect the two entries with a count of 1.
Algorithm
- Create a hash map to store the frequency of each number.
- Iterate through the array, incrementing the count for each number.
- Iterate through the hash map and collect all numbers with a count of 1.
- Return the two numbers found.
Example Walkthrough
Code
- Time Complexity: O(n). We make one pass to build the frequency map and one pass over the map to find the unique elements. Both are linear.
- Space Complexity: O(n). The hash map stores up to n/2 + 2 distinct entries in the worst case.
The hash map approach works, but it uses O(n) extra space to store every distinct element. The problem specifically asks for O(1) space. Can we get rid of the extra storage by sorting the array instead?
Approach 2: Sorting
Intuition
If we sort the array first, duplicate elements end up next to each other. We can then walk through the sorted array in pairs. Whenever two adjacent elements don't match, the first one must be a unique number.
This trades the hash map's space for the sort's time. We get O(1) extra space, but sorting costs O(n log n).
Algorithm
- Sort the array.
- Iterate through the array two elements at a time (i = 0, 2, 4, ...).
- If
nums[i] != nums[i+1], thennums[i]is a unique element. Collect it and advance by 1 (not 2). - Otherwise, advance by 2 (skip the pair).
- If we reach the last element without a partner, it's the second unique number.
Example Walkthrough
Code
- Time Complexity: O(n log n). Dominated by the sort. The subsequent scan is O(n).
- Space Complexity: O(1). We sort in-place and use only a couple of variables (ignoring the sort's internal stack space).
The sorting approach uses O(1) extra space but takes O(n log n) time. The problem asks for O(n) time AND O(1) space. Can we use XOR to let duplicate pairs cancel themselves automatically in a single pass?
Approach 3: Bit Manipulation (XOR)
Intuition
This is where the bit manipulation magic happens. Let's build up the idea step by step.
First, recall the key XOR properties:
a ^ a = 0(any number XOR itself is zero)a ^ 0 = a(any number XOR zero is itself)- XOR is commutative and associative (order doesn't matter)
If we XOR all elements in the array, every number that appears twice cancels itself out, leaving us with x ^ y, where x and y are the two unique numbers. For [1, 2, 1, 3, 2, 5], that gives us 3 ^ 5 = 6 (binary 110).
But that's the XOR of both numbers combined. How do we separate them?
Here's the key insight: since x != y, their XOR has at least one bit set to 1. A set bit at position k means x and y differ at bit k. One of them has a 0 there, the other has a 1. We can use this differentiating bit to split the entire array into two groups:
- Group A: numbers with bit
kset to 1 - Group B: numbers with bit
kset to 0
Every paired number lands in the same group (both copies have the same bit at position k), so they still cancel within their group. But x and y land in different groups. XOR-ing each group separately gives us x and y individually.
The core insight is that XOR is both a combining and a separating tool. When we XOR all elements, duplicate pairs cancel to zero, leaving only x ^ y. But x ^ y alone doesn't tell us what x and y are individually.
The differentiating bit breaks the deadlock. Since x and y are different numbers, they must differ in at least one bit position. By choosing any such bit and partitioning the array, we guarantee:
xandyland in different groups (they differ at this bit).- Every duplicate pair lands in the same group (both copies have the same bits).
So within each group, the problem reduces to the classic Single Number (LeetCode 136). Pairs cancel, and we're left with exactly one unique number per group.
Algorithm
- XOR all elements together to get
xorAll = x ^ y. - Find any set bit in
xorAll. The rightmost set bit is easiest:diffBit = xorAll & (-xorAll). - Partition the array into two groups based on whether each element has
diffBitset. - XOR all elements in each group separately. One group yields
x, the other yieldsy. - Return
[x, y].
Example Walkthrough
Code
- Time Complexity: O(n). Two passes through the array. The first computes the overall XOR, and the second partitions and XOR-s each group. Each pass is O(n).
- Space Complexity: O(1). We use only a constant number of integer variables (
xorAll,diffBit,x). No extra data structures needed.