Single Number
Understanding the Problem
We have an array where every number shows up exactly twice, except for one number that appears only once. Our job is to find that unique number.
Finding which number lacks a pair is easy. The constraint is what makes the problem interesting: we need O(n) time and O(1) space. That rules out sorting (O(n log n)) and hash maps (O(n) space).
The problem is about pairing. Every number has a partner except one. If we can cancel out all the pairs, only the answer remains.
Key Constraints:
nums.length <= 3 * 10^4→ An O(n^2) scan is around 9 * 10^8 comparisons in the worst case, slow enough to time out. We want O(n).-3 * 10^4 <= nums[i] <= 3 * 10^4→ Values can be negative, so index-based counting tricks won't work directly.- Every element appears exactly twice except one → This guarantee is what lets pairs cancel cleanly.
Approach 1: Brute Force (Nested Loops)
Intuition
For each element, check whether it has a duplicate somewhere else in the array. If no duplicate exists, that element is the answer.
We pick each element one by one and scan the rest of the array looking for a match. If we finish scanning without finding one, we have found the single number.
Algorithm
- For each element
nums[i], set a flag indicating no duplicate has been found. - For each other element
nums[j]wherej != i, check ifnums[i] == nums[j]. - If a match is found, mark that a duplicate exists and break the inner loop.
- If no match was found after the inner loop completes, return
nums[i].
Example Walkthrough
Code
- Time Complexity: O(n^2). For each of the n elements, we scan up to n elements looking for a duplicate. In the worst case, the single number is at the end, so we do roughly n * n comparisons.
- Space Complexity: O(1). We only use a boolean flag and loop variables. No extra data structures.
The cost here is the repeated scanning: every element triggers another pass over the array. The next approach removes that by counting occurrences in a single pass.
Approach 2: Hash Map (Count Occurrences)
Intuition
Instead of rescanning the array for every element, count how many times each number appears using a hash map, then return the number whose count is 1.
This trades space for time. One pass builds the frequency map, a second pass finds the element that appears once. Both passes are linear.
Algorithm
- Create a hash map to store the count of each number.
- Iterate through the array. For each number, increment its count in the map.
- Iterate through the map and return the number whose count is 1.
Example Walkthrough
Code
- Time Complexity: O(n). One pass to build the map, one pass to find the single element. Both are O(n).
- Space Complexity: O(n). The hash map stores up to (n+1)/2 unique elements, which is O(n).
This uses O(n) extra space for the hash map, but the problem asks for O(1) space. The next approach cancels out paired elements without storing anything, leaving only the unpaired one.
Approach 3: XOR (Bit Manipulation)
Intuition
The XOR operator has three properties that solve this problem in one pass with no extra storage:
- Self-cancellation:
a ^ a = 0(any number XOR'd with itself becomes 0) - Identity:
a ^ 0 = a(any number XOR'd with 0 stays the same) - Commutativity and Associativity: The order doesn't matter.
a ^ b ^ a = a ^ a ^ b = 0 ^ b = b
XOR all elements together. Because order is irrelevant, the two copies of each paired number sit next to each other in effect and cancel to 0. The single number XORs with 0 and survives. For [a, a, b, b, c], the running XOR reduces to (a ^ a) ^ (b ^ b) ^ c = 0 ^ 0 ^ c = c.
Algorithm
- Initialize a variable
resultto 0. - XOR every element in the array with
result. - After the loop,
resultholds the single number.
Example Walkthrough
Code
- Time Complexity: O(n). We iterate through the array exactly once, performing a constant-time XOR at each step.
- Space Complexity: O(1). We only use a single integer variable
result. No extra data structures needed.