Watch 10 video solutions for Single Number III, a medium level problem involving Array, Bit Manipulation. This walkthrough by take U forward has 149,689 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |