Maximum XOR of Two Numbers in an Array

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.

Example 1:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

Example 2:

Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Output: 127

Constraints:

• 1 <= nums.length <= 2 * 10^5
• 0 <= nums[i] <= 2^31 - 1

Can you provide code to solve this problem efficiently, discuss its time and space complexity, and address potential edge cases?

## Maximum XOR of Two Numbers in an Array

This problem asks us to find the maximum result of `nums[i] XOR nums[j]` within a given integer array `nums`, where `0 <= i <= j < n`.

### 1. Brute Force Solution

A naive approach would be to iterate through all possible pairs of numbers in the array and calculate their XOR, keeping track of the maximum XOR value encountered.  This is simple to implement but inefficient.

```python
def find_maximum_xor_brute_force(nums):
    max_xor = 0
    n = len(nums)
    for i in range(n):
        for j in range(i, n):
            max_xor = max(max_xor, nums[i] ^ nums[j])
    return max_xor

# Example usage:
nums = [3, 10, 5, 25, 2, 8]
print(f"Maximum XOR (Brute Force): {find_maximum_xor_brute_force(nums)}")  # Output: 28

2. Optimal Solution using Trie

A more efficient solution involves using a Trie data structure. The idea is to insert each number's binary representation into the Trie. Then, for each number, we traverse the Trie to find the number that maximizes the XOR value.

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

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, num):
        node = self.root
        for i in range(31, -1, -1):  # Iterate from MSB to LSB
            bit = (num >> i) & 1
            if not node.children[bit]:
                node.children[bit] = TrieNode()
            node = node.children[bit]

    def find_max_xor(self, num):
        node = self.root
        max_xor = 0
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            opposite_bit = 1 - bit
            if node.children[opposite_bit]:
                max_xor |= (1 << i)
                node = node.children[opposite_bit]
            else:
                node = node.children[bit]
            
        return max_xor

def find_maximum_xor_trie(nums):
    trie = Trie()
    for num in nums:
        trie.insert(num)

    max_xor = 0
    for num in nums:
        max_xor = max(max_xor, trie.find_max_xor(num))

    return max_xor

# Example usage:
nums = [3, 10, 5, 25, 2, 8]
print(f"Maximum XOR (Trie): {find_maximum_xor_trie(nums)}")  # Output: 28

3. Big(O) Runtime Analysis

• Brute Force: The brute force approach has a time complexity of O(n^2) because it iterates through all possible pairs of numbers in the array.
• Trie: The Trie approach has a time complexity of O(n * 32), which is effectively O(n), because inserting each number into the Trie takes O(32) time (since we're dealing with 32-bit integers), and finding the maximum XOR for each number also takes O(32) time. The outer loop iterates n times.

4. Big(O) Space Usage Analysis

• Brute Force: The brute force approach has a space complexity of O(1) because it only uses a constant amount of extra space.
• Trie: The Trie approach has a space complexity of O(n), as in the worst-case scenario, all numbers have completely different bit patterns, and each number will add 32 nodes to the Trie. In reality, the space complexity would likely be less than O(n*32) because there could be overlap in the prefixes of the binary representation of numbers.

5. Edge Cases and Handling

• Empty Array: If the input array is empty, the maximum XOR is 0.
• Single Element Array: If the array contains only one element, the maximum XOR is 0 (as there are no pairs).
• Negative Numbers: The problem statement specifies non-negative numbers, but if negative numbers are allowed, the Trie approach will still work since it operates on the bit representation.
• Large Numbers: The code assumes 32-bit integers. If the numbers can be larger, the range in the loops (e.g. range(31, -1, -1)) needs to be adjusted accordingly.

Here's an extended version handling empty or single element array edge cases:

def find_maximum_xor_trie_with_edge_cases(nums):
    if not nums or len(nums) < 2:
        return 0  # Handle empty or single-element array

    trie = Trie()
    for num in nums:
        trie.insert(num)

    max_xor = 0
    for num in nums:
        max_xor = max(max_xor, trie.find_max_xor(num))

    return max_xor