LeetCode 136: Single Number - All Solutions Explained

Problem Statement

The Single Number problem, LeetCode 136, is an easy-difficulty challenge where you’re given an array nums of integers, where every element appears twice except for one. Your task is to find the single number that appears only once, using a solution with linear runtime and no extra space beyond O(1).

Constraints

• 1 ≤ nums.length ≤ 3 * 10^4
• -3 * 10^4 ≤ nums[i] ≤ 3 * 10^4
• Each element appears twice except one, which appears once

Example

Copy codeInput: nums = [2,2,1]
Output: 1
Explanation: 2 appears twice, 1 appears once.

Copy codeInput: nums = [4,1,2,1,2]
Output: 4
Explanation: 1 and 2 appear twice, 4 appears once.

Copy codeInput: nums = [1]
Output: 1
Explanation: Single element appears once.

Understanding the Problem

We need to identify the unique number in an array where all other numbers are paired. Key points:

• Pairs cancel out; the single number remains.
• We need O(n) time and O(1) space.
• We’ll explore two solutions:
  • XOR Operation : Optimal and bit-based (best solution).
  • Hash Map : Intuitive but uses extra space.

Solution 1: XOR Operation (Best Solution)

Intuition

Use the XOR operation’s properties: XOR of a number with itself is 0, and XOR with 0 is the number itself. XORing all numbers cancels pairs, leaving the single number.

How It Works

1. Initialize a variable result to 0.
2. XOR each number in the array with result.
3. Return result, which will be the single number.

Step-by-Step Example

For nums = [4,1,2,1,2]:

• result = 0.
• 0 ^ 4 = 4.
• 4 ^ 1 = 5.
• 5 ^ 2 = 7.
• 7 ^ 1 = 6.
• 6 ^ 2 = 4.
• Result: 4.

Python Code (Best Solution)

Copy codedef singleNumber(nums: list[int]) -> int:
    result = 0
    for num in nums:
        result ^= num
    return result

# Test cases
print(singleNumber([2,2,1]))       # Output: 1
print(singleNumber([4,1,2,1,2]))   # Output: 4
print(singleNumber([1]))           # Output: 1

Detailed Walkthrough

• XOR Property : a ^ a = 0, a ^ 0 = a, commutative and associative.
• Iteration : Pairs cancel to 0, leaving the single number.
• Result : Final value is the unpaired element.

Complexity

• Time Complexity : O(n), single pass through the array.
• Space Complexity : O(1), no extra space used.

Why It’s the Best

• Meets all requirements: linear time, constant space.
• Elegant use of bit manipulation.
• Interview-preferred for its efficiency and ingenuity.

Solution 2: Hash Map

Intuition

Use a hash map to count occurrences of each number, then find the one with a count of 1.

How It Works

1. Create a hash map to store frequency of each number.}
2. Iterate through nums, updating counts.
3. Return the number with a count of 1.

Python Code

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

# Test cases
print(singleNumber([2,2,1]))       # Output: 1
print(singleNumber([4,1,2,1,2]))   # Output: 4
print(singleNumber([1]))           # Output: 1

Detailed Walkthrough

• Hash Map : Tracks frequency of each element.
• Counting : Increments count per occurrence.
• Search : Finds the key with value 1.

Complexity

• Time Complexity : O(n), single pass to build the map and scan it.
• Space Complexity : O(n), for storing the hash map.

Pros and Cons

• Pros : Easy to understand and implement.
• Cons : Uses extra space, violating the O(1) space requirement.

Comparison of Solutions

Table

Edge Cases to Consider

• Single element: [1] → 1.
• Minimum size: [1,1,2] → 2.
• Negative numbers: [-1,-1,2] → 2.
• Large values: Within constraints, XOR still works.

Final Thoughts

• XOR Operation : The best solution—fast, space-efficient, and cleverly uses bit manipulation.
• Hash Map : Useful for learning but not optimal here. Master the XOR approach for its brilliance in single-number problems. Try finding two single numbers in an array as a follow-up!