136. Single Number - Detailed Explanation
Problem statement
Given a non-empty array of integers, every element appears twice except for one. Find that single element.
Note:
Your algorithm should have a linear runtime complexity and use constant extra space.
Example inputs and outputs
-
Example 1:
- Input:
[2, 2, 1] - Output:
1 - Explanation:
The number1appears only once, whereas2appears twice.
- Input:
-
Example 2:
- Input:
[4, 1, 2, 1, 2] - Output:
4 - Explanation:
The number4is the only element that appears once while the others appear twice.
- Input:
Constraints
1 <= nums.length <= 3 * 10^4-3 * 10^4 <= nums[i] <= 3 * 10^4- Every element in the array appears exactly twice except for one.
This question is the standard introduction to the bitwise XOR pattern. XOR, written ^, compares two numbers bit by bit and sets each output bit to 1 only where the two input bits differ. Two consequences of that rule do all the work here: a ^ a = 0, and 0 ^ a = a. XOR is also commutative and associative, so the order of the array does not matter and each pair cancels wherever its two copies happen to sit. That property converts a counting problem into a single accumulator variable, and it reappears in several questions on the list of patterns interviewers reuse. This question also sits on the Blind 75 list. Design Gurus teaches it in the Single Number lesson.
Hints for solving the problem
-
Hash table approach:
- You can count the frequency of each element using a hash table, then identify the one with a count of 1.
-
XOR approach:
- Consider using the bitwise XOR operator.
- Properties of XOR:
a ^ a = 00 ^ a = a
- When you XOR all elements together, the pairs cancel each other, which leaves only the single element.
Approach 1: brute force using a hash table
Explanation
-
Traverse the array and use a dictionary, or hash map, to count the occurrences of each element.
-
Iterate through the hash map to find the element with a count of 1.
-
Time complexity: O(n)
-
Space complexity: O(n) in the worst case.
Python code (brute force)
Java code (brute force)
Approach 2: optimal solution using XOR
Explanation
-
Initialize a variable
resultwith 0. Zero is the identity value for XOR, so it does not disturb the running total. -
Iterate through each number in the array and perform the XOR operation with
result:result ^= num
-
The XOR operation cancels every duplicate number, since
a ^ a = 0, and leaves the unique number behind. -
Time complexity: O(n)
-
Space complexity: O(1)
Trace [4, 1, 2, 1, 2] to see the cancellation. The running result goes 0, 4, 5, 7, 6, and finally 4. The intermediate values look arbitrary, and they do not matter. What matters is that each of 1 and 2 enters the total twice, so both vanish, and only 4 survives.
Python code (optimal XOR)
Java code (optimal XOR)
Complexity analysis
- Brute force (hash table):
- Time complexity: O(n)
- Space complexity: O(n)
- Optimal (XOR):
- Time complexity: O(n)
- Space complexity: O(1)
Both approaches read the array once, so the time complexity matches. The XOR version wins on space, because it replaces the whole frequency map with one integer. That is what satisfies the constant extra space requirement in the note above.
Edge cases
- A single-element array:
- For example,
[x]should returnx. One XOR against the initial 0 returns the element unchanged.
- For example,
- An array with negative numbers:
- The XOR approach works correctly with negative numbers as well, because it operates on the two's complement bit patterns.
- Large arrays:
- Confirm that your solution handles arrays of the maximum allowed size efficiently.
Common mistakes
- Using extra space unnecessarily:
- The hash table approach is correct, but it does not meet the optimal space requirement.
- Incorrect XOR initialization:
- Forgetting to initialize the result to 0, or misusing the XOR operations, leads to a wrong answer.
- Overlooking edge cases:
- Check that your solution handles a single-element array and arrays with negative numbers.
Alternative variations
- Single Number II (LeetCode 137):
- Every element appears three times except for one. A pair of XORs no longer cancels a triple, so this variant needs a different bit manipulation approach.
- Single Number III (LeetCode 260):
- Two numbers appear once while all others appear twice. The task is to find both unique numbers, which means splitting the array by one differing bit.
Related problems for further practice
- Single Number II (LeetCode 137)
- Single Number III (LeetCode 260)
- Missing Number (LeetCode 268)
- Find the Duplicate Number (LeetCode 287)
All three Single Number variants, plus the rest of the bitwise XOR set, are taught in Grokking the Coding Interview. For a short map of the families these questions fall into, see the common LeetCode patterns answer.
GET YOUR FREE
Coding Questions Catalog
$99
$197
$72
