Log inSign up
mediumLeetCodeNot Started

Single Number III

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Bit Manipulation
Solve on LeetCode
Lesson

Problem Statement

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 O(n) and uses only constant extra space O(1).

Example 1 · Example 1: Positive Array:

Input: nums = [1, 2, 1, 3, 2, 5]
Output: [3, 5]
Explanation: 1 and 2 appear twice; 3 and 5 appear once. Returns [3, 5] (or [5, 3]).

Example 2 · Example 2: Negative Elements:

Input: nums = [-1, 0]
Output: [-1, 0]
Explanation: Both elements appear once.

Example 3 · Example 3: Larger Array:

Input: nums = [0, 1]
Output: [1, 0]
Explanation: Returns [1, 0] or [0, 1].

Constraints:

  • 2 <= nums.length <= 3 * 104
  • -231 <= nums[i] <= 231 - 1
  • Each integer in nums will appear twice, only two integers will appear once.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master two-element bitwise partitioning via differentiating bits.
  • Safely handle two's complement negation with INT_MIN in C++ and Java.
  • Achieve optimal O(n) runtime and O(1) memory guarantees.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Two unique elements among duplicate pairs.
  • Linear time O(n) and constant space O(1).
  • Two-bucket parity split.

Algorithmic Decision Tree:

  • Compute xorSum across all numbers.
  • Isolate rightmost set bit diffBit = xorSum & (-xorSum).
  • Maintain group1 and group2 XOR accumulators.

Connected Patterns:

Single NumberSingle Number IIFind Two Non-Repeating Elements

1. Hash Map / Set Frequency Counting

Intuition

Store frequencies in a map or set. Filter elements appearing exactly once.

When to apply: Basic baseline when memory is unconstrained.

Algorithm

  1. Step 1: Build frequency map.
  2. Step 2: Collect keys with frequency == 1.
  3. Step 3: Return result array.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4
5using namespace std;
6
7vector<int> singleNumberBrute(const vector<int>& nums) {
8 unordered_map<int, int> freq;
9 for (int x : nums) freq[x]++;
10 vector<int> res;
11 for (auto& p : freq) {
12 if (p.second == 1) res.push_back(p.first);
13 }
14 return res;
15}
16
17int main() {
18 vector<int> nums = {1, 2, 1, 3, 2, 5};
19 auto res = singleNumberBrute(nums);
20 cout << "Brute: " << res[0] << ", " << res[1] << endl; // 3, 5
21 return 0;
22}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(n)

2. Sorting and Scan

Intuition

Sort nums. Iterate through the array: if nums[i] == nums[i + 1], skip both (i += 2). Otherwise, nums[i] is single (i++).

When to apply: When O(1) space is needed without bit tricks.

Algorithm

  1. Step 1: Sort nums.
  2. Step 2: Loop i = 0 to n - 1.
  3. Step 3: If i + 1 < n and nums[i] == nums[i + 1]: i += 2.
  4. Step 4: Else: push nums[i], i++.
  5. Step 5: Return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7vector<int> singleNumberSort(vector<int> nums) {
8 sort(nums.begin(), nums.end());
9 vector<int> res;
10 int i = 0;
11 while (i < (int)nums.size()) {
12 if (i + 1 < (int)nums.size() && nums[i] == nums[i + 1]) {
13 i += 2;
14 } else {
15 res.push_back(nums[i]);
16 i++;
17 }
18 }
19 return res;
20}
21
22int main() {
23 vector<int> nums = {1, 2, 1, 3, 2, 5};
24 auto res = singleNumberSort(nums);
25 cout << "Sort: " << res[0] << ", " << res[1] << endl; // 3, 5
26 return 0;
27}

Time & Space Complexity

  • Time complexity: O(n log n)
  • Space complexity: O(1) auxiliary

3. Two-Bucket Bitwise XOR Partitioning

Intuition

Compute diff = a ^ b across all numbers. Isolate the lowest set bit using diffBit = diff & (-diff) (casted safely to unsigned to prevent overflow). XOR elements where (x & diffBit) != 0 into a, and elements where (x & diffBit) == 0 into b. Return [a, b].

When to apply: Optimal canonical solution for Single Number III.

Algorithm

  1. Step 1: Compute diff = nums[0] ^ nums[1] ^ ... ^ nums[n - 1].
  2. Step 2: Isolate lowest set bit: diffBit = (unsigned int)diff & -(unsigned int)diff.
  3. Step 3: Initialize a = 0, b = 0.
  4. Step 4: For each x in nums: if (x & diffBit) != 0: a ^= x; else: b ^= x.
  5. Step 5: Return {a, b}.

Partitioning Trace: nums = [1, 2, 1, 3, 2, 5]

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Compute XOR of all elements: 1^2^1^3^2^5 = 3^5 = 6 (binary 110)
Visual state
Values and pointers at this exact step
pointers
S
110
0
↑ 3 ^ 5
Check / comparison
diff = 6 (110_2)
Decision / next transition
Set bits indicate differing positions between 3 and 5.
Why this step matters

Step 1: Compute XOR of all elements: 12^13^25 = 35 = 6 (binary 110). diff = 6.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7public:
8 vector<int> singleNumber(vector<int>& nums) {
9 long long diff = 0;
10 for (int x : nums) diff ^= x;
11
12 long long diffBit = diff & (-diff);
13 int a = 0, b = 0;
14 for (int x : nums) {
15 if (x & diffBit) {
16 a ^= x;
17 } else {
18 b ^= x;
19 }
20 }
21 return {a, b};
22 }
23};
24
25int main() {
26 Solution sol;
27 vector<int> nums = {1, 2, 1, 3, 2, 5};
28 auto res = sol.singleNumber(nums);
29 cout << "Optimal: " << res[0] << ", " << res[1] << endl; // 3, 5
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Hash Map / SetO(n)O(n)Track frequencies in a map or set; elements with count 1 are returned.Memory allocation.
2.Better — SortingO(n log n)O(1) auxiliarySort the array and scan in steps of 2 to identify unpaired elements.Comparison sorting.
3.Optimal — Two-Bucket Bitwise XOR PartitioningOptimalO(n)O(1)Find diff = a ^ b, isolate differentiating bit diffBit, accumulate XOR in two buckets.Two linear scans.

Common Pitfalls & Crucial Edge Cases

Integer overflow on `diff & -diff`

If diff = -2147483648, negating it in signed 32-bit int overflows. In C++/Java, use diff & -(unsigned)diff or diff & -diff in 64-bit int.

Using a Hash Set

Takes O(n) extra space, failing the O(1) space constraint.

Wrong partition check

Writing if (num & mask == 1) instead of if ((num & mask) != 0). The isolated bit mask has value 2k, not necessarily 1.

Crucial Edge Cases to Validate:

  • Array of length 2 `[x, y]` — Directly returns [x, y].
  • One or both unique numbers are negative — Handled cleanly in two's complement.
  • diff = INT_MIN (0x80000000) — In C++, -INT_MIN overflows signed int. Cast diff to unsigned int before computing diff & -diff.
  • Ordering of output pair — Check if the problem accepts any order or requires sorted order.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Emphasize the discriminator bit idea: any set bit in x ^ y is a proof of difference between x and y.
  2. Show how you handle the diff = INT_MIN edge case safely with unsigned casting.
  3. Clarify the return format (e.g. [x, y] in ascending order or any order).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What does XORing all elements in Single Number III yield?

2.How do you distinguish between x and y using diff = x ^ y?

3.What is the time and space complexity of this algorithm?

Back to DSA Sheet