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 - 1nums will appear twice, only two integers will appear once.Problem Overview: You're given an integer array where every element appears exactly twice except for two numbers that appear once. The task is to return those two unique values. Order does not matter, but the solution should run in linear time and ideally constant extra space.
Approach 1: Counting with HashMap (O(n) time, O(n) space)
The straightforward solution uses a frequency map. Iterate through the array and store counts in a hash map where the key is the number and the value is its frequency. After building the map, iterate through the entries and collect the numbers with frequency 1. Since all other numbers appear exactly twice, the two values with count 1 are the answer.
This approach relies on constant‑time hash lookups and works well for quick implementation. The tradeoff is memory usage: the hash map can grow up to O(n) in the worst case. It mainly serves as a conceptual baseline before optimizing with bit tricks. Related concepts appear often in hash table problems involving frequency counting.
Approach 2: XOR and Partitioning (O(n) time, O(1) space)
The optimal solution uses properties of XOR. First XOR all elements in the array. Since a ^ a = 0, every duplicated value cancels out. The final XOR result equals x ^ y, where x and y are the two unique numbers.
The key insight: if x ^ y is non‑zero, at least one bit differs between them. Extract the rightmost set bit using diff = xor & -xor. This bit acts as a partition. Iterate through the array again and divide numbers into two groups based on whether this bit is set. Because duplicates share identical bits, they fall into the same group and cancel via XOR. Each partition eventually produces one of the unique numbers.
This technique keeps memory usage constant and requires only two passes over the array. It is a classic application of bit manipulation combined with simple iteration over an array. The partitioning trick appears frequently in interview problems involving XOR identities.
Recommended for interviews: Interviewers typically expect the XOR partitioning solution. The HashMap approach shows that you understand the problem and can build a correct baseline, but the XOR method demonstrates deeper knowledge of bit operations and space optimization. If time permits, explain the HashMap idea briefly and then implement the XOR solution for the final answer.
The idea is to use the XOR operation to find two unique numbers that appear only once in the array. This can be achieved by:
This C program uses bitwise XOR to isolate the unique numbers. The key step is identifying a differing bit to partition the numbers, allowing separation of the unique numbers in linear time.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), constant space is used for variables non-dependent on input size.
An alternative approach that utilizes hash maps to count occurrences of each element would typically find the unique numbers. Although this solution is more straightforward, it requires additional space and does not strictly meet the problem constraints of constant extra space.
This Python solution leverages collections.Counter to track occurrences and quickly find numbers appearing only once. While simple, it utilizes additional space beyond the constraints of the problem for learning purposes.
Python
Time Complexity: O(n), for passing through the array for counting.
Space Complexity: O(n), as space is allocated for counts of numbers.
The XOR operation has the following properties:
x \oplus 0 = x;x \oplus x = 0;Since all numbers in the array appear twice except for two numbers, we can perform XOR operation on all numbers in the array to get the XOR result of the two numbers that only appear once.
Since these two numbers are not equal, there is at least one bit that is 1 in the XOR result. We can use the lowbit operation to find the lowest bit of 1 in the XOR result, and divide all numbers in the array into two groups based on whether this bit is 1 or not. This way, the two numbers that only appear once are separated into different groups.
Perform XOR operation on each group separately to obtain the two numbers a and b that only appear once.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| XOR and Partitioning | Time Complexity: O(n), where n is the length of the array. |
| Counting with HashMap (Conceptual) | Time Complexity: O(n), for passing through the array for counting. |
| Bitwise Operation | — |
| Hash Table | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Counting with HashMap | O(n) | O(n) | Quick baseline solution when memory constraints are not strict |
| XOR and Partitioning | O(n) | O(1) | Optimal interview solution with constant extra space |
L7. Single Number III | Bit Manipulation • take U forward • 149,689 views views
Watch 9 more video solutions →Practice Single Number III with our built-in code editor and test cases.
Practice on FleetCode