LeetCode 260: Single Number III Solution in Python – A Step-by-Step Guide

What Is LeetCode 260: Single Number III?

In LeetCode 260: Single Number III, you’re given an integer array nums where every number appears twice except for two, which appear once. Your task is to return those two unique numbers in any order. This problem builds on LeetCode 136: Single Number, where only one number was unique, adding a twist with two to find.

Problem Statement

• Input: An integer array nums.
• Output: A list of two integers—the numbers that appear once.
• Rules: All numbers except two appear twice; return the two singles in any order.

Constraints

• Array length: 2 to 10^4 (even length).
• Values: -2^31 to 2^31 - 1.
• Exactly two numbers appear once, others twice.

Examples

• Input: nums = [1,2,1,3,2,5]
• Output: [3,5] (1 and 2 appear twice, 3 and 5 once).
• Input: nums = [0,1]
• Output: [0,1] (each appears once).
• Input: nums = [1,1,2,2,3,4]
• Output: [3,4].

Understanding the Problem: Finding the Odd Ones Out

To solve LeetCode 260: Single Number III in Python, we need to spot two numbers in an array that don’t have a pair, while every other number does. For example, in [1,2,1,3,2,5], 1 pairs with 1, 2 with 2, but 3 and 5 stand alone. A basic way—counting each number’s appearances—works but uses extra space. We’ll use two methods: 1. Best Solution (Bit Manipulation with XOR): O(n) time—fast and space-saving. 2. Alternative Solution (Hash Map): O(n) time—simple but uses more memory.

Let’s dive into the best solution with a friendly, detailed walkthrough.

Best Solution: Bit Manipulation with XOR

Why This Is the Best Solution

The bit manipulation approach using XOR is the top pick for LeetCode 260 because it runs in O(n) time and uses O(1) space—just a few variables, no extra storage. It’s a clever trick that uses binary math to separate the two unique numbers, making it both fast and elegant once you get the hang of it.

How It Works

Think of this solution as a detective game with a secret code: XOR, a tool that cancels out pairs and highlights differences. We use it to find the two single numbers by splitting them apart based on their bits. Here’s how it works, step-by-step, explained simply:

• Step 1: XOR All Numbers:
• XOR (^ in Python) is like a magic switch: same numbers cancel (e.g., 2 ^ 2 = 0), different ones leave a trace.
• XOR all numbers in the array. Pairs cancel out, leaving the XOR of the two singles (call them A and B).
• Example: [1,2,1,3,2,5] → 1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5 = (1 ^ 1) ^ (2 ^ 2) ^ 3 ^ 5 = 0 ^ 0 ^ 3 ^ 5 = 3 ^ 5 = 6.
• Step 2: Find a Difference Bit:
• The result (e.g., 6) is A ^ B. Since A and B are different, this number isn’t 0, and some bit is 1 where A and B differ.
• Pick any 1-bit in A ^ B (e.g., 6 in binary is 110, so use the rightmost 1: 2).
• Use diff & -diff to get this bit (it isolates the rightmost 1).
• Step 3: Split the Numbers:
• Divide the array into two groups:
• Numbers where that bit is 1.
• Numbers where that bit is 0.
• A and B will split into different groups because they differ at this bit.
• Step 4: XOR Each Group:
• XOR all numbers in each group:
• Group with bit 1: Pairs cancel, leaves one single (e.g., A).
• Group with bit 0: Leaves the other (e.g., B).
• Step 5: Combine Results:
• You’ve got A and B—return them!

It’s like sorting socks with a magic wand: XOR finds the mismatch, and bits split the odd ones apart!

Step-by-Step Example

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

• Step 1: XOR All:
• 1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5 = (1 ^ 1) ^ (2 ^ 2) ^ 3 ^ 5 = 0 ^ 0 ^ 3 ^ 5 = 6.
• diff = 6 (3 ^ 5).
• Step 2: Find Rightmost 1-Bit:
• 6 in binary = 110.
• diff & -diff = 6 & -6 = 110 & (111...110) = 010 = 2 (rightmost 1).
• Step 3: Split into Groups:
• Bit at position (2’s place):
• 1 = 001, 0 & 2 = 0.
• 2 = 010, 2 & 2 = 2.
• 1 = 001, 0 & 2 = 0.
• 3 = 011, 2 & 2 = 2.
• 2 = 010, 2 & 2 = 2.
• 5 = 101, 0 & 2 = 0.
• Group 1 (bit 1): [2, 3, 2].
• Group 0 (bit 0): [1, 1, 5].
• Step 4: XOR Each Group:
• Group 1: 2 ^ 3 ^ 2 = (2 ^ 2) ^ 3 = 0 ^ 3 = 3.
• Group 0: 1 ^ 1 ^ 5 = (1 ^ 1) ^ 5 = 0 ^ 5 = 5.
• Step 5: Result:
• [3, 5].
• Result: [3,5].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained in a friendly way:

Copy codeclass Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        # Step 1: XOR all numbers to get A ^ B
        diff = 0
        for num in nums:
            diff ^= num  # XOR cancels pairs, leaves A ^ B

        # Step 2: Find the rightmost 1-bit in diff
        # This bit differs between A and B
        diff &= -diff  # Isolates rightmost 1 (e.g., 6 & -6 = 2)

        # Step 3: Split into two groups and XOR
        num1, num2 = 0, 0
        for num in nums:
            if num & diff:  # Bit is 1
                num1 ^= num  # XOR into first group
            else:  # Bit is 0
                num2 ^= num  # XOR into second group

        # Step 4: Return the two single numbers
        return [num1, num2]

• Time Complexity: O(n)—one pass to XOR, one to split.
• Space Complexity: O(1)—just two variables.

This solution is like a bit magic show—XOR and split, and the singles appear!

Alternative Solution: Hash Map Approach

Why an Alternative Approach?

The hash map method counts how many times each number appears, like tallying votes, then picks out the ones with a count of 1. It’s slower on space but easier to picture, making it a nice way to start before diving into bits.

How It Works

Imagine you’re counting how many times each friend shows up to a party. Most come in pairs, but two come alone—those are your targets. Here’s how it works, step-by-step:

• Step 1: Build a Count Map:
• Use a dictionary to track each number’s appearances.
• Step 2: Find the Singles:
• Look for numbers with a count of 1.
• Step 3: Collect Them:
• Put those two numbers in a list.

It’s like checking a guest list—spot the loners!

Step-by-Step Example

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

• Step 1: Count:
• Map: {1: 2, 2: 2, 3: 1, 5: 1}.
• Step 2: Find Singles:
• 3: count 1.
• 5: count 1.
• Step 3: Result:
• [3, 5].
• Result: [3,5].

Code for Hash Map Approach

Copy codeclass Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        # Step 1: Build the count map
        count_map = {}
        for num in nums:
            count_map[num] = count_map.get(num, 0) + 1

        # Step 2: Find numbers with count 1
        result = []
        for num, freq in count_map.items():
            if freq == 1:
                result.append(num)

        return result

• Time Complexity: O(n)—one pass to build, one to scan.
• Space Complexity: O(n)—hash map size.

It’s a clear path but uses more space.

Comparing the Two Solutions

• Best Solution (XOR):
• Pros: O(n) time, O(1) space, clever.
• Cons: Bit logic might feel tricky.
• Alternative Solution (Hash Map):
• Pros: Simple counting.
• Cons: O(n) space, less efficient.

XOR wins for space and flair.

Additional Examples and Edge Cases

Minimal Case

• [0,1] → [0,1]

Negative Numbers

• [-1,-1,2,3] → [2,3]

Large Array

• [1,1,2,2,3,4] → [3,4]

Both handle these well.

Complexity Breakdown

• XOR:
• Time: O(n)—two passes.
• Space: O(1)—minimal.
• Hash Map:
• Time: O(n)—two passes.
• Space: O(n)—map.

XOR is leaner.

Key Takeaways

• XOR: Cancels pairs, finds differences.
• Bits: Split numbers with a 1-bit trick.
• Hash Map: Count and filter—easy to see.
• Python Tip: XOR (^) is powerful—see [Python Basics](/python/basics).

Final Thoughts: Spot Singles Like a Pro

LeetCode 260: Single Number III in Python is a clever number hunt. The XOR solution dazzles with bit magic, while the hash map lays it out simply. Want more? Try LeetCode 136: Single Number or LeetCode 137: Single Number II. Ready to sleuth? Head to Solve LeetCode 260 on LeetCode and find those singles today!