Problem Description

You are given an integer array nums. Your task is to find the maximum XOR (exclusive OR) value that can be obtained by selecting any two elements from the array.

Specifically, you need to calculate nums[i] XOR nums[j] for all valid pairs where 0 <= i <= j < n (where n is the length of the array), and return the maximum value among all these XOR operations.

The XOR operation between two numbers compares their binary representations bit by bit - it returns 1 when the bits are different and 0 when they are the same.

For example, if nums = [3, 10, 5, 25, 2, 8], you would compute XOR for all possible pairs:

• 3 XOR 3 = 0
• 3 XOR 10 = 9
• 3 XOR 5 = 6
• ... and so on

The maximum XOR value from all these pairs would be your answer.

The solution uses a Trie (prefix tree) data structure to efficiently find the maximum XOR. The Trie stores the binary representation of each number, allowing us to greedily select the opposite bit at each position when searching for the number that would produce the maximum XOR with a given number. This approach processes each bit from the most significant to the least significant (bits 30 to 0 for 32-bit integers), trying to maximize the XOR result by choosing the opposite bit whenever possible.

Intuition

To maximize the XOR between two numbers, we need to understand what makes XOR large. XOR returns 1 when bits are different and 0 when they're the same. Therefore, to maximize the XOR result, we want to find pairs of numbers whose bits differ as much as possible, especially in the higher-order (more significant) bit positions since they contribute more to the final value.

The key insight is that for any given number, we want to find another number in the array that has opposite bits in as many positions as possible, starting from the most significant bit. For instance, if we have a number whose binary representation starts with 101..., we'd ideally want to find a number that starts with 010... to maximize the XOR.

A brute force approach would compare every pair, taking O(n²) time. However, we can optimize this using a Trie structure to store binary representations of all numbers. The Trie allows us to make greedy choices bit by bit.

Here's the clever part: when we insert numbers into the Trie, we're essentially creating paths based on their binary representation. Each node has at most two children (0 or 1). When searching for the maximum XOR partner for a number, we traverse the Trie and at each level (representing each bit position from high to low), we try to go down the opposite branch if it exists. If the current bit is 0, we prefer to go down the 1-branch, and vice versa.

For example, if we're at a bit position where our number has a 1, and the Trie has a branch for 0 at that position, we take it because 1 XOR 0 = 1, contributing to a larger result. If the opposite branch doesn't exist, we have no choice but to follow the same bit branch, resulting in 1 XOR 1 = 0 or 0 XOR 0 = 0 for that position.

This greedy approach works because we process bits from most significant to least significant, and maximizing higher-order bits always leads to a larger number regardless of the lower-order bits. The time complexity becomes O(n * 31) for insertion and searching, where 31 is the number of bits we consider for each integer.

Solution Approach

The solution implements a binary Trie (prefix tree) to efficiently find the maximum XOR value. Let's walk through the implementation step by step:

Trie Data Structure

The Trie class has a children attribute that stores exactly two possible children (for bits 0 and 1):

• children[0]: represents the path when the current bit is 0
• children[1]: represents the path when the current bit is 1

Insert Operation

The insert method adds a number to the Trie by processing its binary representation:

def insert(self, x: int):
    node = self
    for i in range(30, -1, -1):
        v = x >> i & 1
        if node.children[v] is None:
            node.children[v] = Trie()
        node = node.children[v]

• We iterate from bit position 30 down to 0 (covering 31 bits total)
• For each bit position i, we extract the bit using x >> i & 1
  • x >> i shifts the number right by i positions
  • & 1 extracts the least significant bit
• If the child node for this bit doesn't exist, we create it
• We then move to that child node and continue

Search Operation

The search method finds the maximum XOR value for a given number against all numbers in the Trie:

def search(self, x: int) -> int:
    node = self
    ans = 0
    for i in range(30, -1, -1):
        v = x >> i & 1
        if node.children[v ^ 1]:
            ans |= 1 << i
            node = node.children[v ^ 1]
        else:
            node = node.children[v]
    return ans

• Again, we process bits from position 30 down to 0
• For each bit v of the input number, we check if the opposite bit v ^ 1 exists in the Trie
  • If v = 0, then v ^ 1 = 1 (we want to find 1)
  • If v = 1, then v ^ 1 = 0 (we want to find 0)
• If the opposite bit exists:
  • We set the corresponding bit in our answer using ans |= 1 << i
  • We traverse to the opposite branch
• If the opposite bit doesn't exist:
  • We're forced to take the same bit path (contributing 0 to XOR)
  • We traverse to the available branch

Main Solution

The findMaximumXOR method orchestrates the entire process:

def findMaximumXOR(self, nums: List[int]) -> int:
    trie = Trie()
    for x in nums:
        trie.insert(x)
    return max(trie.search(x) for x in nums)

1. First, we build the Trie by inserting all numbers from the array
2. Then, for each number in the array, we search for its maximum XOR partner
3. We return the maximum XOR value found across all numbers

The time complexity is O(n * 31) for both building the Trie and searching, where n is the number of elements. The space complexity is O(n * 31) in the worst case for storing the Trie structure.

Example Walkthrough

Let's walk through a small example with nums = [3, 10, 5] to illustrate how the Trie-based solution finds the maximum XOR.

Step 1: Convert numbers to binary (5-bit representation for simplicity)

• 3 = 00011
• 10 = 01010
• 5 = 00101

Step 2: Build the Trie by inserting all numbers

Inserting 3 (00011):

     root
      |
     [0]
      |
     [0]
      |
     [0]
      |
     [1]
      |
     [1]

Inserting 10 (01010):

     root
    /    \
   [0]    [0]
    |      |
   [0]    [1]
    |      |
   [0]    [0]
    |      |
   [1]    [1]
    |      |
   [1]    [0]

Inserting 5 (00101):

     root
    /    \
   [0]    [0]
    |      |
   [0]    [1]
    |    /   \
   [0]  [0]  [1]
    |    |    |
   [1]  [1]  [0]
    |    |    |
   [1]  [0]  [1]

Step 3: Search for maximum XOR for each number

Searching for 3 (00011):

• Bit 4: Current bit is 0, want 1 → 1 doesn't exist, must take 0 → XOR bit = 0
• Bit 3: Current bit is 0, want 1 → 1 doesn't exist, must take 0 → XOR bit = 0
• Bit 2: Current bit is 0, want 1 → 1 exists! Take it → XOR bit = 1
• Bit 1: Current bit is 1, want 0 → 0 exists! Take it → XOR bit = 1
• Bit 0: Current bit is 1, want 0 → 0 doesn't exist, must take 1 → XOR bit = 0

Result: 00110 = 6 (this is 3 XOR 5)

Searching for 10 (01010):

• Bit 4: Current bit is 0, want 1 → 1 doesn't exist, must take 0 → XOR bit = 0
• Bit 3: Current bit is 1, want 0 → 0 exists! Take it → XOR bit = 1
• Bit 2: Current bit is 0, want 1 → 1 exists! Take it → XOR bit = 1
• Bit 1: Current bit is 1, want 0 → 0 exists! Take it → XOR bit = 1
• Bit 0: Current bit is 0, want 1 → 1 exists! Take it → XOR bit = 1

Result: 01111 = 15 (this is 10 XOR 5)

Searching for 5 (00101):

• Bit 4: Current bit is 0, want 1 → 1 doesn't exist, must take 0 → XOR bit = 0
• Bit 3: Current bit is 0, want 1 → 1 doesn't exist, must take 0 → XOR bit = 0
• Bit 2: Current bit is 1, want 0 → 0 exists! Take it → XOR bit = 1
• Bit 1: Current bit is 0, want 1 → 1 exists! Take it → XOR bit = 1
• Bit 0: Current bit is 1, want 0 → 0 exists! Take it → XOR bit = 1

Result: 00111 = 7 (this is 5 XOR 3 or 5 XOR 10? Actually checking: 5 XOR 10 = 15, 5 XOR 3 = 6, so this path gives us 5 XOR 10 = 15)

Step 4: Return maximum Maximum XOR = max(6, 15, 15) = 15

The answer is 15, which corresponds to 10 XOR 5.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n * L) where n is the number of elements in the input array and L is the number of bits (31 bits for integers up to 2^31).

• Building the Trie: The insert method is called n times, and each insertion traverses through 31 bits (from bit position 30 to 0), performing constant-time operations at each level. This gives us O(n * 31) = O(n * L).

• Finding maximum XOR: The search method is called n times (once for each number), and each search traverses through 31 bits, performing constant-time operations at each level. This also gives us O(n * 31) = O(n * L).

• Total time complexity: O(n * L) + O(n * L) = O(n * L), which simplifies to O(31n) = O(n) since 31 is a constant.

Space Complexity: O(n * L) where n is the number of elements and L is the number of bits (31 bits).

• In the worst case, each number in the array could have a completely unique bit pattern, requiring a unique path in the Trie.

• Each number requires up to 31 nodes to be stored (one for each bit position from 30 to 0).

• With n numbers and potentially 31 nodes per number, the space complexity is O(n * 31) = O(n * L).

• Since 31 is a constant, this can be simplified to O(n) in terms of the input size.

Common Pitfalls

1. Incorrect Bit Range Handling

Pitfall: A common mistake is using an incorrect range for bit positions. Developers might use range(31, -1, -1) thinking they need to process all 32 bits, but this can cause issues when dealing with negative numbers or when the constraint specifies non-negative integers only.

Why it happens: The problem states we're dealing with non-negative integers, and the maximum value in typical constraints is often less than 2^31. Using bit position 31 would include the sign bit in signed integer representation, which can lead to unexpected behavior.

Solution: The code correctly uses range(30, -1, -1) to process 31 bits (positions 0-30), which is sufficient for positive integers up to 2^31 - 1.

2. Forgetting to Handle Missing Opposite Bit Path

Pitfall: When searching for the maximum XOR, forgetting to handle the case where the opposite bit path doesn't exist in the Trie:

# WRONG - This will crash with NoneType error
def search(self, num: int) -> int:
    current_node = self
    max_xor = 0
    for bit_position in range(30, -1, -1):
        bit_value = (num >> bit_position) & 1
        opposite_bit = bit_value ^ 1
        # Always trying to go opposite without checking
        max_xor |= (1 << bit_position)
        current_node = current_node.children[opposite_bit]  # Can be None!
    return max_xor

Solution: Always check if the opposite path exists before traversing:

if current_node.children[opposite_bit] is not None:
    max_xor |= (1 << bit_position)
    current_node = current_node.children[opposite_bit]
else:
    current_node = current_node.children[bit_value]

3. Incorrect XOR Result Accumulation

Pitfall: Incorrectly updating the XOR result when the opposite bit is found:

# WRONG - Adding instead of OR-ing the bit
max_xor += (1 << bit_position)

# WRONG - Always setting the bit regardless of path taken
for bit_position in range(30, -1, -1):
    bit_value = (num >> bit_position) & 1
    max_xor |= (1 << bit_position)  # Wrong! Only set when opposite bit found

Solution: Only set the bit in the result when we successfully take the opposite path:

if current_node.children[opposite_bit] is not None:
    max_xor |= (1 << bit_position)  # Set bit only when XOR would be 1

4. Edge Case: Single Element Array

Pitfall: Not considering that with a single element, the only valid pair is the element with itself, which always gives XOR = 0:

# Potential issue if not handled properly
nums = [5]
# XOR of 5 with itself is 0, not 5

Solution: The current implementation handles this correctly because:

• The Trie will contain only one number
• When searching, it will follow the exact same path, resulting in XOR = 0
• The logic naturally handles this without special casing

5. Memory Optimization Oversight

Pitfall: Using a full class with unnecessary overhead for Trie nodes:

# Less efficient
class Trie:
    def __init__(self):
        self.children = [None, None]
        self.is_end = False  # Not needed for this problem!
        self.value = None    # Not needed!

Solution: The implementation correctly uses __slots__ and only stores the essential children array:

class Trie:
    __slots__ = ("children",)  # Memory optimization
  
    def __init__(self):
        self.children = [None, None]  # Only what's needed