LeetCode 421: Maximum XOR of Two Numbers in an Array Solution in Python – A Step-by-Step Guide

What Is LeetCode 421: Maximum XOR of Two Numbers in an Array?

In LeetCode 421: Maximum XOR of Two Numbers in an Array, you’re given an integer array nums (e.g., [3, 10, 5, 25, 2, 8]), and you need to return the maximum result of XORing any two numbers in the array. XOR (exclusive OR) compares bits: 1 XOR 0 = 1, 0 XOR 0 = 0, 1 XOR 1 = 0, so the goal is to find a pair with the largest possible bitwise difference. For example, in [3, 10, 5, 25, 2, 8], the maximum XOR is 25 XOR 8 = 17 (binary 11001 XOR 01000 = 10001). You’re looking for the biggest flip you can get!

Problem Statement

• Input: An integer array nums.
• Output: An integer—the maximum XOR of any two numbers in nums.
• Rules:
• Use the XOR operation (^ in Python).
• Pick any two numbers (can be the same index if allowed, but typically distinct pairs).

Constraints

• 1 <= nums.length <= 2 * 10⁴.
• 0 <= nums[i] < 2³¹.

Examples

• Input: nums = [3,10,5,25,2,8]
• Output: 28 (25 XOR 8 = 28, not 17 as corrected below).
• Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
• Output: 127 (e.g., 83 XOR 36).
• Input: nums = [0]
• Output: 0 (single number XOR itself).

Understanding the Problem: Maximizing the XOR

To solve LeetCode 421: Maximum XOR of Two Numbers in an Array in Python, we need to find two numbers in nums whose XOR yields the largest value. XOR maximizes when bits differ (1 XOR 0), so we’re seeking a pair with the most contrasting binary patterns. A naive approach might be to XOR every pair—but with up to 2 * 10⁴ elements, that’s 10⁸ operations! Instead, we’ll use:

• Best Solution (Trie-Based Approach): O(n * 32) time, O(n * 32) space—uses a Trie for efficiency.
• Alternative Solution (Brute Force Iteration): O(n²) time, O(1) space—checks all pairs.

Let’s dive into the Trie-based solution with a clear, step-by-step explanation.

Best Solution: Trie-Based Approach

Why This Is the Best Solution

The Trie-based approach is the top pick because it’s fast—O(n * 32) time, O(n * 32) space—and cleverly uses a binary Trie to find the maximum XOR without checking every pair. It builds a Trie of all numbers’ binary representations, then for each number, searches for the best opposite bit pattern to maximize the XOR. It’s like building a bit-by-bit map and hunting for the perfect mismatch!

How It Works

Think of the numbers as binary strings you’re matching:

• Step 1: Build the Trie:
• For each number, convert to 32-bit binary (e.g., 3 = 000...11).
• Insert into a Trie: 0 or 1 branches at each bit position.
• Step 2: Find Max XOR:
• For each number:
• Traverse Trie, prefer opposite bits (1 if 0, 0 if 1).
• Build max XOR value bit-by-bit.
• Step 3: Track Maximum:
• Compare each XOR result, keep the largest.
• Step 4: Why This Works:
• Trie stores all numbers’ bits, enabling fast lookups.
• Opposite bits maximize XOR (e.g., 1 XOR 0 > 1 XOR 1).
• It’s like finding the most different twin for each number!

Step-by-Step Example

Example: nums = [3,10,5,25,2,8]

• Binary (simplified to 5 bits for clarity, actual is 32):
• 3 = 00011
• 10 = 01010
• 5 = 00101
• 25 = 11001
• 2 = 00010
• 8 = 01000
• Build Trie:
• Root → 0 (all), 1 (25).
• Bit 2: 0 → 0 (3,5,2,8), 1 (10); 1 → 1 (25).
• Continue to bit 0, forming paths.
• Find Max XOR:
• For 3 (00011):
• Prefer 1: 1 (25), 0: 0 (all), 1: 0 (10,8), 1: 1 (none, take 0), 0: 0 (10) → 10100 = 20.
• Max so far = 20.
• For 10 (01010):
• Prefer 1: 1 (25), 0: 0 (all), 1: 0 (3,5,2,8), 0: 1 (3,5), 1: 0 (2,8) → 10101 = 21.
• Max = 21.
• For 25 (11001):
• Prefer 0: 0 (all but 25), 1: 0 (10,8), 0: 1 (3,5), 0: 1 (5), 1: 0 (2,8) → 00110 = 6, try others → 25 XOR 2 = 27.
• Max = 27.
• Continue: 25 XOR 8 = 28 (11001 XOR 01000 = 11101).
• Result: 28.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so you can follow every step:

Copy codeclass TrieNode:
    def __init__(self):
        self.children = [None, None]  # 0 and 1 bits

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        # Step 1: Build Trie
        root = TrieNode()
        for num in nums:
            node = root
            for i in range(31, -1, -1):  # 32 bits
                bit = (num >> i) & 1      # Get bit at position i
                if not node.children[bit]:
                    node.children[bit] = TrieNode()
                node = node.children[bit]

        # Step 2: Find max XOR
        max_xor = 0
        for num in nums:
            node = root
            curr_xor = 0
            for i in range(31, -1, -1):
                bit = (num >> i) & 1
                # Try opposite bit if exists
                opp_bit = 1 - bit
                if node.children[opp_bit]:
                    curr_xor |= (1 << i)  # Add 2^i to XOR
                    node = node.children[opp_bit]
                else:
                    node = node.children[bit]
            max_xor = max(max_xor, curr_xor)

        return max_xor

• Line 1-4: TrieNode class:
• children: Two slots for 0 and 1 bits.
• Line 8-16: Build Trie:
• Line 10-15: For each num, loop 32 bits (MSB to LSB):
• Extract bit with shift and mask (e.g., 3 >> 1 & 1 = 1).
• Add node if missing, move down.
• Line 19-31: Find max XOR:
• Line 21-29: For each num:
• Start at root, build curr_xor.
• Line 23-29: For each bit:
• Prefer opposite bit (opp_bit) to maximize XOR.
• If exists, add 2^i (shift left), move to opp_bit.
• Else, move to same bit.
• Update max_xor.
• Line 33: Return max XOR.
• Time Complexity: O(n * 32)—n numbers, 32 bits each.
• Space Complexity: O(n * 32)—Trie nodes.

This is like building a binary map to find the ultimate XOR mismatch!

Alternative Solution: Brute Force Iteration

Why an Alternative Approach?

The brute force iteration method checks every pair of numbers, XORing them to find the maximum. It’s O(n²) time and O(1) space—simple but slow for large arrays. It’s like testing every handshake in a room to find the wildest clash!

How It Works

Picture it as pairing up numbers:

• Step 1: Loop through all pairs (i, j).
• Step 2: XOR each pair, track max.
• Step 3: Return the largest result.

Step-by-Step Example

Example: nums = [3,10,5,25,2,8]

• Pairs:
• 3 ^ 10 = 9
• 3 ^ 5 = 6
• 3 ^ 25 = 26
• 3 ^ 2 = 1
• 3 ^ 8 = 11
• 10 ^ 5 = 15
• 10 ^ 25 = 19
• 10 ^ 2 = 8
• 10 ^ 8 = 2
• 5 ^ 25 = 28
• 5 ^ 2 = 7
• 5 ^ 8 = 13
• 25 ^ 2 = 27
• 25 ^ 8 = 17
• 2 ^ 8 = 10
• Result: Max = 28 (5 ^ 25).

Code for Brute Force Approach

Copy codeclass Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        max_xor = 0
        n = len(nums)

        for i in range(n):
            for j in range(i + 1, n):
                curr_xor = nums[i] ^ nums[j]
                max_xor = max(max_xor, curr_xor)

        return max_xor

• Time Complexity: O(n²)—all pairs checked.
• Space Complexity: O(1)—just a variable.

It’s a slow pair-tester!

Comparing the Two Solutions

• Trie-Based (Best):
• Pros: O(n * 32), O(n * 32), fast and scalable.
• Cons: Trie complexity.
• Brute Force (Alternative):
• Pros: O(n²), O(1), simple.
• Cons: Too slow.

Trie wins for speed.

Additional Examples and Edge Cases

• [0]: 0.
• [1,2]: 3.
• [8,10,2]: 10.

Trie handles all.

Complexity Breakdown

• Trie: Time O(n * 32), Space O(n * 32).
• Brute Force: Time O(n²), Space O(1).

Trie’s the champ.

Key Takeaways

• Trie: Bitwise hunt!
• Brute Force: Pair it up!
• XOR: Flips rule.
• Python Tip: Bits rock—see [Python Basics](/python/basics).

Final Thoughts: Max That XOR

LeetCode 421: Maximum XOR of Two Numbers in an Array in Python is a bitwise adventure. Trie-based zips to the max, while brute force trudges through. Want more bit fun? Try LeetCode 136: Single Number or LeetCode 191: Number of 1 Bits. Ready to XOR? Head to Solve LeetCode 421 on LeetCode and flip those bits today!