Given a non-empty array `nums` where every element appears exactly twice except for one, find that single one. Solve it with O(1) extra space.
Example: nums = [4, 1, 2, 1, 2] → 4
Count with a map: Tally every value, then return the one with a count of 1. (time O(n), space O(n))
No visualization loaded.
Watch
—
i
Press Run to begin.
Why the best approach wins
The map approach works but pays for a whole tally table — O(n) extra memory. XOR uses the algebra of bits instead: every value XOR'd with itself becomes 0, so duplicates erase each other and only the lone value remains. One pass, a single integer of memory: O(1) space.
Count with a map: O(n) time / O(n) spaceXOR everything: O(n) time / O(1) space
Your turn — implement singleNumber
Loading editor…