Single Number
Every element in nums appears twice except for one, which appears once. Return that single element using constant extra space and linear time.
Intuition
The counting instinct is to tally every value in a hash map and then look for the tally of one. That works, but the map is doing more than we need — we never care how many times a number appeared, only whether it cancelled out. XOR is exactly a cancelling operation: a ^ a = 0 and a ^ 0 = a. So XOR every element together and the pairs annihilate each other, leaving the loner standing alone.
Approach
Start with the map, and notice what it over-collects
Walk the array and store value → count in a hash map, then walk the map and return whichever key has a count of 1. This is correct and easy to defend in an interview. But look at what the map holds at the end: for [4,1,2,1,2] it stores 4→1, 1→2, 2→2. Every entry except one is a pair we already know is irrelevant. We are paying O(n) memory to record facts we immediately throw away — and the interviewer will push back on exactly that extra space.
Find an operation that makes pairs disappear
We want the duplicates to erase themselves as we walk, so nothing needs storing. XOR does this: a ^ a = 0 for any a, and a ^ 0 = a. XOR is also commutative and associative, which is the part that really matters — it means the pairs do not have to be adjacent. The array order is irrelevant; we can mentally regroup 4 ^ 1 ^ 2 ^ 1 ^ 2 into 4 ^ (1 ^ 1) ^ (2 ^ 2), which collapses to 4 ^ 0 ^ 0, which is just 4.
Fold the whole array into one running value
Initialise ans = 0 — the identity for XOR — and XOR each element into it as you scan. Every paired value contributes twice and cancels to nothing; the unpaired value contributes once and survives. One pass, one integer of memory, and no dependence on the array being sorted or the duplicates being neighbours.
Solution & live demo
Edge cases
0 ^ 7 = 7. The loop runs once and returns the only element, which is by definition the single number.
XOR operates on the two's-complement bit pattern, so signs are handled automatically. -3 ^ -3 is still 0.
Works: 1 ^ 1 ^ 0 = 0. Because we return the accumulator rather than checking for a sentinel, a legitimate 0 answer is indistinguishable from no answer only if the input were empty — which the constraints forbid.