LeetCode · #136
Single Number Solution
Every element appears twice except one. Find the single element in O(n) time and O(1) space.
01
Section One · Problem
Problem Statement
Given a non-empty array where every element appears twice except one, find that single one. Must run in O(n) time and O(1) extra space.
Example
Input: nums = [4,1,2,1,2]
Output: 4
Constraints
• 1 ≤ nums.length ≤ 3 × 10⁴ • Each element appears twice except one
02
Section Two · Approach 1
HashMap — O(n) time, O(n) space
Count frequencies. Return the element with count 1.
Problem: O(n) space. XOR gives O(1) space because
a ⊕ a = 0 and a ⊕ 0 = a. All duplicates cancel out, leaving only the single number.Java — HashMap
import java.util.*;
class Solution {
public int singleNumber(int[] nums) {
Map<Integer,Integer> map = new HashMap<>();
for (int n : nums) map.merge(n, 1, Integer::sum);
for (var e : map.entrySet())
if (e.getValue() == 1) return e.getKey();
return -1;
}
}
Python — Counter
from collections import Counter
class Solution:
def singleNumber(self, nums: list[int]) -> int:
return [k for k, v in Counter(nums).items() if v == 1][0]
03
Section Three · Approach 2
XOR — O(n) time, O(1) space
XOR all elements. Since a ⊕ a = 0 and a ⊕ 0 = a, all duplicates cancel out, leaving only the single number.
💡 Mental model: Imagine a light switch. Each number "flips" a switch. If a number appears twice, it flips on then off — canceling out. After all flips, the only switch still on is the single number. XOR is that light switch — same value twice returns to zero.
🎯 When to recognize this pattern: "Find the element that appears odd times when all others appear even times." XOR is the tool. Key properties: commutative, associative, self-inverse. Also used in LC 268 (Missing Number), LC 137 (Single Number II — bit counting for triples), LC 260 (Single Number III — two unique numbers).
04
Section Four · Trace
Visual Walkthrough
XOR — Duplicates Cancel
05
Section Five · Implementation
Code — Java & Python
Java — XOR
class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for (int n : nums) res ^= n;
return res;
}
}
Python — XOR (reduce)
from functools import reduce
from operator import xor
class Solution:
def singleNumber(self, nums: list[int]) -> int:
return reduce(xor, nums)
06
Section Six · Analysis
Complexity Analysis
| Approach | Time | Space |
|---|---|---|
| HashMap | O(n) | O(n) |
| Sort + scan | O(n log n) | O(1) |
| XOR ← optimal | O(n) | O(1) |
07
Section Seven · Edge Cases
Edge Cases & Pitfalls
| Case | Input | Why It Matters |
|---|---|---|
| Single element | [42] | 0 ⊕ 42 = 42. |
| Negative numbers | [-1,1,-1] | XOR works on negative ints (two's complement). |
| Zero is single | [0,1,1] | 0 is valid. XOR: 0⊕1⊕1 = 0. |
⚠ Common Mistake: Trying to solve with
sum(set) * 2 - sum(array). This works mathematically but can overflow for large values. XOR has no overflow risk and is the cleanest solution.