LeetCode 137: Single Number II Solution in Python Explained

Problem Statement

In LeetCode 137, you’re given an integer array nums where every element appears exactly three times except for one element, which appears once. Your task is to return the element that appears only once, ideally in O(n) time and O(1) extra space. This builds on LeetCode 136: Single Number, where pairs canceled out, but now we handle triplets, differing from candy distribution like LeetCode 135: Candy.

Constraints

• 1 <= nums.length <= 3 * 10^4
• -2^31 <= nums[i] <= 2^31 - 1
• Each element appears three times except one, which appears once

Example

Let’s see some cases:

Copy codeInput: nums = [2,2,3,2]
Output: 3
Explanation: 2 appears thrice, 3 appears once.

Copy codeInput: nums = [0,1,0,1,0,1,99]
Output: 99
Explanation: 0 and 1 appear thrice, 99 appears once.

Copy codeInput: nums = [-2,-2,1,1,-3,1,-2]
Output: -3
Explanation: -2 and 1 appear thrice, -3 appears once.

These examples show we’re isolating a singleton among triplets.

Understanding the Problem

How do you solve LeetCode 137: Single Number II in Python? Take nums = [2,2,3,2]. We need the number appearing once—2 appears three times, 3 appears once, so return 3. For [0,1,0,1,0,1,99], 0 and 1 triplet, leaving 99. Simple XOR from LeetCode 136 won’t work (triplets don’t cancel), so we need a method to handle three occurrences. This isn’t a gas station circuit like LeetCode 134: Gas Station; it’s about array-based singleton detection. We’ll use: 1. Bitwise Manipulation with 32-bit Tracking: 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: Bitwise Manipulation with 32-bit Tracking Approach

Explanation

Bitwise Manipulation with 32-bit Tracking counts the occurrences of each bit across all numbers, using modulo 3 to isolate bits of the single number (since triplet bits sum to 0 mod 3). It tracks each of the 32 bits of an integer, building the result by setting bits where the count mod 3 is 1. This is the best solution due to its O(n) time complexity, O(1) space (using only a fixed 32-bit integer), and clever use of bitwise operations to meet the problem’s optimal constraints, avoiding extra data structures.

For [2,2,3,2]:

• Bit 0: 0+0+1+0 = 1 mod 3 = 1.
• Bit 1: 1+1+1+1 = 4 mod 3 = 1.
• Bit 2+: All 0.
• Result: 11 binary = 3.

Step-by-Step Example

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

Goal: Return 3.

• Start: bits = [0]*32.
• Step 1: Process 2 (binary 10).
• Bit 1: 1, bits[1] = 1.
• Step 2: Process 2 (binary 10).
• Bit 1: 1+1=2, bits[1] = 2.
• Step 3: Process 3 (binary 11).
• Bit 0: 1, bits[0] = 1.
• Bit 1: 2+1=3 mod 3 = 0, bits[1] = 0.
• Step 4: Process 2 (binary 10).
• Bit 1: 0+1=1, bits[1] = 1.
• Result: bits = [1,1,0,...], build 11 binary = 3.
• Finish: Return 3.

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

Goal: Return 99.

• Start: bits = [0]*32.
• Step 1: 0, no change.
• Step 2: 1 (binary 1), bits[0] = 1.
• Step 3-4: 0, 0, no change.
• Step 5: 1 (binary 1), bits[0] = 2.
• Step 6: 1 (binary 1), bits[0] = 3 mod 3 = 0.
• Step 7: 99 (binary 1100011).
• bits[0] = 1, bits[1] = 1, bits[5] = 1, bits[6] = 1.
• Result: bits = [1,1,0,0,0,1,1,0,...], build 1100011 = 99.
• Finish: Return 99.

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

Goal: Return -3.

• Start: Handle negatives via 32-bit signed integers.
• Process: Triplets (-2, 1) cancel mod 3, -3 remains.
• Result: Bitwise sum yields -3 (11111101 in 2’s complement).
• Finish: Return -3.

How the Code Works (Bitwise Manipulation with 32-bit Tracking) – 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
    # Will hold the single number (e.g., initially 0)

    # Line 2: Iterate over each bit position (0 to 31)
    for i in range(32):
        # i = bit position (e.g., 0 for least significant bit)

        # Line 3: Count occurrences of 1s at bit i
        bit_sum = 0
        for num in nums:
            # num = current number (e.g., 2, 3)
            bit_sum += (num >> i) & 1
            # Shifts right by i, masks with 1 (e.g., 2>>1=1&1=1, 3>>0=1&1=1)
            # Counts 1s at position i

        # Line 4: Modulo 3 to find single number’s bit
        bit_sum %= 3
        # Triplets yield 0 mod 3, single yields 1 (e.g., 4%3=1 for bit 1)

        # Line 5: Set bit in result if 1
        if bit_sum:
            # If bit_sum = 1 (e.g., bit 0), set bit i
            result |= bit_sum << i
            # Shifts 1 left by i, ORs with result (e.g., 1<<0=1, result=1)

    # Line 6: Handle negative numbers (32-bit signed integer)
    if result > 2**31 - 1:  # Max positive 32-bit int
        result -= 2**32
        # Adjusts for 2’s complement (e.g., -3 from 4294967293)

    # Line 7: Return the single number
    return result
    # Final value (e.g., 3 for [2,2,3,2])

This detailed breakdown clarifies how bitwise manipulation isolates the single number.

Alternative: Hash Map Counting Approach

Explanation

Hash Map Counting uses a dictionary to count occurrences, finding the number with a count of 1. It’s a practical alternative, easy to implement, but uses O(n) space, less optimal than bitwise manipulation for this problem’s constraints.

For [2,2,3,2]:

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

Step-by-Step Example (Alternative)

For [0,1,0,1,0,1,99]:

• Start: count = {}.
• Step: count = {0:3, 1:3, 99:1}.
• Find: Key with value 1 is 99.
• Finish: Return 99.

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 constraints

Complexity

• Bitwise Manipulation with 32-bit Tracking:
• Time: O(n) – 32 passes over n elements, effectively O(n).
• Space: O(1) – constant space (32-bit integer).
• Hash Map Counting:
• Time: O(n) – two passes.
• Space: O(n) – hash map storage.

Efficiency Notes

Bitwise Manipulation with 32-bit Tracking is the best solution with O(n) time and O(1) space, meeting optimal constraints elegantly—Hash Map Counting matches time complexity but uses O(n) space, making it simpler but less space-efficient.

Key Insights

• Bitwise: Triplets mod 3 cancel.
• Hash Map: Counts occurrences.
• Triplets: Three appearances dominate.

Additional Example

For nums = [5,2,5,2,5]:

• Goal: 2.
• Bitwise: 5s cancel, 2 remains.

Edge Cases

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

Both solutions handle these well.

Final Thoughts

LeetCode 137: Single Number II in Python is a fascinating bitwise puzzle. The Bitwise Manipulation with 32-bit Tracking solution excels with its efficiency and ingenuity, while Hash Map Counting offers a clear approach. Want more? Try LeetCode 136: Single Number for the simpler version or LeetCode 94: Binary Tree Inorder Traversal for tree basics. Ready to practice? Solve LeetCode 137 on LeetCode with [2,2,3,2], aiming for 3—test your skills now!