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 are 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 numbers. Order does not matter. The challenge is doing this in linear time without using extra memory.
Approach 1: Counting with HashMap (O(n) time, O(n) space)
Traverse the array and store the frequency of each number using a hash map. Each insertion or update is an average O(1) operation. After building the map, iterate over the key-value pairs and collect the numbers whose frequency equals 1. Those two values are the answer. This approach is straightforward and easy to implement, but it uses additional memory proportional to the number of distinct elements. It relies on hash lookups and works well when space usage is not a concern. The idea uses a standard counting pattern commonly seen with array frequency problems.
Approach 2: XOR and Partitioning (O(n) time, O(1) space)
The optimal solution relies on properties of bit manipulation. First XOR all numbers in the array. Since duplicate numbers cancel out (a ^ a = 0), the final XOR result equals x ^ y, where x and y are the two unique numbers. Because x and y are different, their XOR must have at least one set bit. Extract the rightmost set bit using diff = xor & -xor. This bit distinguishes the two numbers.
Next partition the array into two groups based on whether this bit is set. One unique number falls into each group, while duplicates still cancel within their group. XOR the numbers inside each partition to recover the two unique values. This works because identical numbers always land in the same partition and eliminate each other. The algorithm scans the array twice and stores only a few integers, keeping space complexity constant.
Recommended for interviews: Interviewers typically expect the XOR partitioning approach. The HashMap solution shows correct reasoning and is acceptable as a first step, but the O(n) time and O(1) space XOR method demonstrates strong understanding of bit manipulation and optimization techniques. Being able to derive the separating bit and explain why duplicates cancel out is the key signal of mastery.
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.
C++
Java
Python
C#
JavaScript
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.
Time Complexity: O(n), for passing through the array for counting.
Space Complexity: O(n), as space is allocated for counts of numbers.
| 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. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Counting with HashMap | O(n) | O(n) | Simple implementation when extra memory is acceptable |
| XOR and Partitioning | O(n) | O(1) | Optimal solution expected in interviews and memory‑constrained environments |
L7. Single Number III | Bit Manipulation • take U forward • 83,833 views views
Watch 9 more video solutions →Practice Single Number III with our built-in code editor and test cases.
Practice on FleetCode