Single Number III
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.
With a single unique number, this would be the classic Single Number problem (LeetCode 136), where XOR-ing all elements gives the answer directly: every duplicate cancels itself, leaving the lone value. With two unique numbers, one XOR pass gives the XOR of both unknowns combined into a single value. Separating that combined value back into the two original numbers is the harder part.
The problem asks for O(n) time and O(1) space, which rules out a hash map (O(n) space) and sorting (O(n log n) time). Both still solve the problem and are worth understanding, so we build up to the bit-manipulation solution that meets both constraints.
Key Constraints:
-2^31 <= nums[i] <= 2^31 - 1→ Values span the full signed 32-bit range, including negatives. Any bit-level reasoning has to account for the sign bit and for the combined XOR equallingINT_MIN.- Exactly two elements appear once, every other appears twice → This even/odd structure is what XOR exploits: paired values vanish, leaving only the two singletons.
Approach 1: Hash Map
Intuition
Count how many times each number appears, then pick out the two that appear once. A hash map gives O(1) average lookups and updates, so building the counts takes one linear pass.
After counting, a second pass over the map collects every entry whose count is 1. There are exactly two such entries.
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 uses O(n) extra space to store every distinct element, which violates the O(1) space requirement. Sorting removes that extra storage by grouping duplicates together instead of recording counts.
Approach 2: Sorting
Intuition
Once the array is sorted, the two copies of every duplicate sit next to each other. Walking through the sorted array in pairs, each matched pair occupies two adjacent slots. When an element does not equal its neighbor, the run of pairs has broken, and that element is one of the singletons.
This replaces the hash map's extra space with sorting time: O(1) extra space (sorting in place) at the cost of 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).
Sorting gives O(1) extra space but O(n log n) time, still short of the O(n) time target. XOR reaches both bounds at once by letting duplicate pairs cancel without any sorting or extra storage.
Approach 3: Bit Manipulation (XOR)
Intuition
XOR has three properties that drive the whole approach:
a ^ a = 0(a number XOR itself is zero)a ^ 0 = a(a number XOR zero is itself)- XOR is commutative and associative, so the order of operations does not change the result
XOR-ing every element in the array makes each duplicate pair cancel to zero, leaving x ^ y, where x and y are the two singletons. For [1, 2, 1, 3, 2, 5], the result is 3 ^ 5 = 6 (binary 110). That combined value still hides the individual numbers, so the second step splits it apart.
Because x != y, the value x ^ y has at least one bit set to 1. A bit set at position k means x and y differ there: one has a 0 at bit k, the other has a 1. That single differing bit partitions the entire array into two groups:
- Group A: numbers with bit
kset to 1 - Group B: numbers with bit
kset to 0
The two copies of any duplicate share identical bits, so both copies fall in the same group and still cancel there. The singletons x and y differ at bit k, so they fall in different groups. XOR-ing each group on its own then recovers x from one group and y from the other.
The partition is valid because of two guarantees that hold for any chosen differing bit k:
- Both copies of a duplicate have identical bits, so they share the same value at bit
kand land in the same group. Their contributions cancel within that group. xandydiffer at bitkby construction, so they land in different groups.
Each group therefore contains one singleton plus some number of complete duplicate pairs. XOR-ing a group cancels every pair to zero and returns the one singleton, which is the LeetCode 136 case applied to each half.
Algorithm
- XOR all elements together to get
xorAll = x ^ y. - Isolate any one set bit of
xorAll. The rightmost set bit is the simplest to extract:diffBit = xorAll & (-xorAll). - XOR only the elements that have
diffBitset. That group holds one singleton plus complete pairs, so the running XOR collapses to a single valuex. - Recover the other singleton as
xorAll ^ x. SincexorAll = x ^ y, the termxorAll ^ xequalsy, which avoids a second filtered pass. - Return
[x, xorAll ^ x].
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.