LeetCode 136: Single Number — From Naive Map to Elegant XOR

We've all been there in a coding interview: you read a problem, and your brain immediately jumps to the easiest, most intuitive solution. You build a hash map, track frequencies, and call it a day. It works, it's fast, and it passes all test cases.

But then the interviewer drops the hammer: "Can you solve it in linear time $\mathcal{O}(n)$ and constant extra space $\mathcal{O}(1)$?"

This is the exact progression of LeetCode 136: Single Number. In this decode, we’ll walk through the problem, analyze the constraints, and progress from the naive approaches to the elegant, bitwise XOR solution that interviewers look for.

The Core Problem

Given a non-empty array of integers nums, every element appears twice except for one. We need to find that single, unique element.

The Real Constraint

The challenge isn't just finding the number; it's doing so under the strict rules of the universe:

• Time: $\mathcal{O}(n)$ (You can only scan the array a constant number of times).
• Space: $\mathcal{O}(1)$ (You cannot allocate extra memory that scales with the input size).

Read the original LeetCode 136 Problem →

Approach 1: The Intuitive Naive Way (Hash Map / Set)

The most natural way to track duplicates is to keep count of how many times each number appears. We can iterate through the array and store the counts in a hash map.

Python Solution (Naive Map)

def singleNumber(nums: list[int]) -> int:
    counts = {}
    for num in nums:
        counts[num] = counts.get(num, 0) + 1
        
    for num, count in counts.items():
        if count == 1:
            return num
    return -1

C++ Solution (Naive Map)

#include <vector>
#include <unordered_map>
 
int singleNumber(std::vector<int>& nums) {
    std::unordered_map<int, int> counts;
    for (int num : nums) {
        counts[num]++;
    }
    for (auto const& [key, val] : counts) {
        if (val == 1) return key;
    }
    return -1;
}

Java Solution (Naive Map)

import java.util.HashMap;
import java.util.Map;
 
class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (entry.getValue() == 1) {
                return entry.getKey();
            }
        }
        return -1;
    }
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(n)$ — We scan the array of size $n$ to populate the map, then scan the map.
• Space Complexity: $\mathcal{O}(n)$ — In the worst-case scenario, we store up to $n/2 + 1$ unique elements in the map. This fails the constant space constraint.

Approach 2: The Sorting Compromise ($\mathcal{O}(1)$ Space, $\mathcal{O}(n \log n)$ Time)

If we cannot allocate extra memory, what if we reorganize the data? By sorting the array first, all duplicates will sit right next to each other.

1. Sort the array.
2. Step through the array by increments of 2 (i += 2).
3. If nums[i] != nums[i + 1], then nums[i] is our single number.
4. If we reach the end of the array, the last element is the single number.

Python Solution (Sorting)

def singleNumber(nums: list[int]) -> int:
    nums.sort()
    for i in range(0, len(nums) - 1, 2):
        if nums[i] != nums[i + 1]:
            return nums[i]
    return nums[-1]

C++ Solution (Sorting)

#include <vector>
#include <algorithm>
 
int singleNumber(std::vector<int>& nums) {
    std::sort(nums.begin(), nums.end());
    for (size_t i = 0; i < nums.size() - 1; i += 2) {
        if (nums[i] != nums[i + 1]) {
            return nums[i];
        }
    }
    return nums.back();
}

Java Solution (Sorting)

import java.util.Arrays;
 
class Solution {
    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i += 2) {
            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }
        return nums[nums.length - 1];
    }
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(n \log n)$ — The sorting step takes $\mathcal{O}(n \log n)$ time, which violates the linear time requirement.
• Space Complexity: $\mathcal{O}(1)$ (or $\mathcal{O}(n)$ depending on the language's sorting algorithm implementation like Timsort in Python/Java, which allocates metadata arrays).

Approach 3: The Optimal Way (Bit Manipulation / XOR)

To satisfy both $\mathcal{O}(n)$ time and $\mathcal{O}(1)$ space, we have to look past standard containers and sorting. We must drop down to the bitwise level.

Enter the XOR (Exclusive OR) operator, represented by the caret symbol ^.

XOR operates on binary bits. It returns 1 if the bits are different, and 0 if they are the same. This leads to three fundamental mathematical properties:

Because of the commutative and associative laws, if we XOR every element in the array together, the duplicate values will group together and cancel out, leaving exactly the single number behind.

Visualizing the cancellation:

Let's trace nums = [4, 1, 2, 1, 2]: $4 \oplus 1 \oplus 2 \oplus 1 \oplus 2$ $= 4 \oplus (1 \oplus 1) \oplus (2 \oplus 2)$ $= 4 \oplus 0 \oplus 0$ $= 4$

Python Solution (Optimal XOR)

def singleNumber(nums: list[int]) -> int:
    unique = 0
    for num in nums:
        unique ^= num
    return unique

C++ Solution (Optimal XOR)

#include <vector>
 
int singleNumber(std::vector<int>& nums) {
    int unique = 0;
    for (int num : nums) {
        unique ^= num;
    }
    return unique;
}

Java Solution (Optimal XOR)

class Solution {
    public int singleNumber(int[] nums) {
        int unique = 0;
        for (int num : nums) {
            unique ^= num;
        }
        return unique;
    }
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(n)$ — We scan the array of size $n$ exactly once.
• Space Complexity: $\mathcal{O}(1)$ — We use a single, scalar integer variable (unique) to store the XOR sum, using zero auxiliary data structures.

Summary of Tradeoffs

Understanding bitwise shortcuts is what separates standard code from optimal systems programming. The next time you see duplicate cancellation in an interview, think XOR first!