LeetCode 136: Single Number Solution in Python Explained

Problem Statement

In LeetCode 136, you’re given an integer array nums where every element appears exactly twice except for one element, which appears once. Your task is to return the element that appears only once, with the solution ideally running in O(n) time and using O(1) extra space. This differs from candy distribution like LeetCode 135: Candy, focusing on identifying a unique element in a paired array rather than allocating resources.

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

Let’s see some cases:

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.

These examples show we’re finding the unpaired number.

Understanding the Problem

How do you solve LeetCode 136: Single Number in Python? Take nums = [2,2,1]. We need the number appearing once—2 pairs up, leaving 1, so return 1. For [4,1,2,1,2], 1 and 2 pair up, leaving 4. This isn’t a gas station circuit like LeetCode 134: Gas Station; it’s about isolating a singleton in a paired array. We’ll use: 1. XOR Bitwise Operation: O(n) time, O(1) space—our best solution. 2. Hash Map Counting: O(n) time, O(n) space—an alternative.

Let’s dive into the best solution.

Best Solution: XOR Bitwise Operation Approach

Explanation

XOR Bitwise Operation leverages the XOR properties: a ^ a = 0 (same numbers cancel) and a ^ 0 = a (identity), plus commutativity. Since every number appears twice except one, XORing all elements cancels pairs, leaving the single number. This is the best solution due to its O(n) time complexity, O(1) space usage (no extra data structures), and elegant use of bitwise operations, perfectly meeting the problem’s optimal constraints.

For [2,2,1]:

• 2 ^ 2 = 0 (pair cancels).
• 0 ^ 1 = 1 (single remains).
• Result: 1.

Step-by-Step Example

Example 1: nums = [2,2,1]

Goal: Return 1.

• Start: result = 0.
• Step 1: result = 0 ^ 2 = 2.
• Step 2: result = 2 ^ 2 = 0 (2 XOR 2 cancels).
• Step 3: result = 0 ^ 1 = 1.
• Finish: Return 1.

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

Goal: Return 4.

• Start: result = 0.
• Step 1: result = 0 ^ 4 = 4.
• Step 2: result = 4 ^ 1 = 5 (binary 100 ^ 001 = 101).
• Step 3: result = 5 ^ 2 = 7 (101 ^ 010 = 111).
• Step 4: result = 7 ^ 1 = 6 (111 ^ 001 = 110).
• Step 5: result = 6 ^ 2 = 4 (110 ^ 010 = 100).
• Finish: Return 4.

Example 3: nums = [1]

Goal: Return 1.

• Start: result = 0.
• Step 1: result = 0 ^ 1 = 1.
• Finish: Return 1.

How the Code Works (XOR Bitwise Operation) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef singleNumber(nums: list[int]) -> int:
    # Line 1: Initialize result
    result = 0
    # Starting value for XOR (e.g., 0)
    # Will hold the single number after all operations

    # Line 2: Iterate through the array
    for num in nums:
        # num = current element (e.g., 2, then 2, then 1)

        # Line 3: XOR current number with result
        result ^= num
        # Updates result with XOR (e.g., 0 ^ 2 = 2, 2 ^ 2 = 0, 0 ^ 1 = 1)
        # Pairs cancel (a ^ a = 0), single number remains (a ^ 0 = a)

    # Line 4: Return the single number
    return result
    # Final value is the unpaired number (e.g., 1 for [2,2,1])

This detailed breakdown clarifies how the XOR bitwise operation efficiently isolates the single number.

Alternative: Hash Map Counting Approach

Explanation

Hash Map Counting uses a dictionary to count occurrences of each number, then finds the one with a count of 1. It’s a practical alternative, straightforward to implement and understand, but uses O(n) space, making it less optimal than XOR for this problem’s constraints.

For [2,2,1]:

• Count: {2:2, 1:1}.
• Find count 1: 1.

Step-by-Step Example (Alternative)

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

• Start: count = {}.
• Step 1: count = {4:1}.
• Step 2: count = {4:1, 1:1}.
• Step 3: count = {4:1, 1:1, 2:1}.
• Step 4: count = {4:1, 1:2, 2:1}.
• Step 5: count = {4:1, 1:2, 2:2}.
• Find: Key with value 1 is 4.
• Finish: Return 4.

How the Code Works (Hash Map Counting)

Copy codedef singleNumberHash(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
    return -1  # Unreachable due to problem constraints

Complexity

• XOR Bitwise Operation:
• Time: O(n) – single pass.
• Space: O(1) – no extra space.
• Hash Map Counting:
• Time: O(n) – two passes (counting, finding).
• Space: O(n) – hash map storage.

Efficiency Notes

XOR Bitwise Operation is the best solution with O(n) time and O(1) space, meeting the problem’s optimal constraints with elegance—Hash Map Counting matches time complexity but uses O(n) space, making it a reliable but less space-efficient alternative, useful for clarity or when XOR isn’t preferred.

Key Insights

• XOR: Cancels pairs, keeps single.
• Hash Map: Counts occurrences.
• Pairs: Every number doubles except one.

Additional Example

For nums = [7,1,5,3,6,3,1,5,6]:

• Goal: 7.
• XOR: Pairs cancel, 7 remains.

Edge Cases

• Single Element: [1] → 1.
• All Pairs Plus One: [2,2,3] → 3.
• Negative Numbers: [-1,-1,2] → 2.

Both solutions handle these well.

Final Thoughts

LeetCode 136: Single Number in Python is a brilliant bitwise challenge. The XOR Bitwise Operation solution excels with its efficiency and minimalism, while Hash Map Counting offers a clear, intuitive approach. Want more? Try LeetCode 137: Single Number II for a twist or LeetCode 94: Binary Tree Inorder Traversal for tree basics. Ready to practice? Solve LeetCode 136 on LeetCode with [2,2,1], aiming for 1—test your skills now!