Watch 10 video solutions for Single Number III, a medium level problem involving Array, Bit Manipulation. This walkthrough by take U forward has 83,833 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 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.
| 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 |