<p>Given an integer array <code>nums</code>, return <em>the maximum result of </em><code>nums[i] XOR nums[j]</code>, where <code>0 &lt;= i &lt;= j &lt; n</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 2 * 10<sup>5</sup></code></li>
	<li><code>0 &lt;= nums[i] &lt;= 2<sup>31</sup> - 1</code></li>
</ul>

class TrieNode:
    def __init__(self):
        self.children = [None, None]  # Only 0 and 1 can be children
        
class Trie:
    def __init__(self, n):
        self.root = TrieNode()  # Root node
        self.n = n  # Max bit length of all numbers
        
    def add_num(self, num):
        node = self.root
        for shift in range(self.n, -1, -1):  # Traverse bits from MSB to LSB
            bit = (num >> shift) & 1  # Get current bit (0 or 1)
            if not node.children[bit]:  # If no node for this bit, create one
                node.children[bit] = TrieNode()
            node = node.children[bit]
        
class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        max_len = len(bin(max(nums))) - 2  # Get max binary length of numbers
        trie = Trie(max_len)
        for num in nums: 
            trie.add_num(num)  # Build Trie
        
        max_xor = 0
        for num in nums:  # For each number, find the maximum XOR with any other number
            node = trie.root
            current_xor = 0
            for shift in range(max_len, -1, -1):
                bit = (num >> shift) & 1  # Get current bit of num
                opposite_bit = 1 - bit  # Try to maximize XOR by using the opposite bit
                if node.children[opposite_bit]:
                    current_xor |= (1 << shift)  # Set this bit in XOR result
                    node = node.children[opposite_bit]
                else:
                    node = node.children[bit]  # If opposite bit not available, take the same bit
            max_xor = max(max_xor, current_xor)  # Update maximum XOR found
        return max_xor


# class TrieNode:
#     def __init__(self):
#         self.children = dict()                        # children nodes
#         self.val = 0                                  # end value 

# class Trie:
#     def __init__(self, n):
#         self.root = TrieNode()                        # root node
#         self.n = n                                    # max length of all numbers
        
#     def add_num(self, num):
#         node = self.root 
#         for shift in range(self.n, -1, -1):           # only shift self.n bits 
#             val = 1 if num & (1 << shift) else 0      # verify bit from left to right 
#             if val not in node.children:
#                 node.children[val] = TrieNode()
#             node = node.children[val]
#         node.val = num
        
# class Solution:
#     def findMaximumXOR(self, nums: List[int]) -> int:
#         max_len = len(bin(max(nums))) - 2             # get max length of all numbers' binary
#         trie = Trie(max_len)
#         for num in nums: trie.add_num(num)            # build trie
            
#         ans = 0
#         for num in nums:                              # for each num, find the number which can create max value with num using XOR
#             node = trie.root 
#             for shift in range(max_len, -1, -1):
#                 val = 1 if num & (1 << shift) else 0  # verify bit from left to right
#                 node = node.children[1-val] if 1-val in node.children else node.children[val] # try opposite bit first, otherwise use same bit
#             ans = max(ans, num ^ node.val)            # maintain maximum
#         return ans    
473034