<p>You are given a <strong>0-indexed</strong> integer array <code>nums</code>. A pair of integers <code>x</code> and <code>y</code> is called a <strong>strong</strong> pair if it satisfies the condition:</p>

<ul>
	<li><code>|x - y| &lt;= min(x, y)</code></li>
</ul>

<p>You need to select two integers from <code>nums</code> such that they form a strong pair and their bitwise <code>XOR</code> is the <strong>maximum</strong> among all strong pairs in the array.</p>

<p>Return <em>the <strong>maximum</strong> </em><code>XOR</code><em> value out of all possible strong pairs in the array</em> <code>nums</code>.</p>

<p><strong>Note</strong> that you can pick the same integer twice to form a pair.</p>

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

<pre>
<strong>Input:</strong> nums = [1,2,3,4,5]
<strong>Output:</strong> 7
<strong>Explanation:</strong> There are 11 strong pairs in the array <code>nums</code>: (1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5) and (5, 5).
The maximum XOR possible from these pairs is 3 XOR 4 = 7.
</pre>

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

<pre>
<strong>Input:</strong> nums = [10,100]
<strong>Output:</strong> 0
<strong>Explanation:</strong> There are 2 strong pairs in the array nums: (10, 10) and (100, 100).
The maximum XOR possible from these pairs is 10 XOR 10 = 0 since the pair (100, 100) also gives 100 XOR 100 = 0.
</pre>

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

<pre>
<strong>Input:</strong> nums = [500,520,2500,3000]
<strong>Output:</strong> 1020
<strong>Explanation:</strong> There are 6 strong pairs in the array nums: (500, 500), (500, 520), (520, 520), (2500, 2500), (2500, 3000) and (3000, 3000).
The maximum XOR possible from these pairs is 500 XOR 520 = 1020 since the only other non-zero XOR value is 2500 XOR 3000 = 636.
</pre>

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

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

# # TRIE TEMPLATE THAT I USE
# # ADD/SEARCH/REMOVE, assume all are of the same length
# class TrieNode:
#     def __init__(self):
#         self.children = {}

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

#     def add(self, word):
#         node = self.root
#         for char in word:
#             if char not in node.children:
#                 node.children[char] = TrieNode()
#             node = node.children[char]

#     def search(self, word):
#         node = self.root
#         for char in word:
#             if char not in node.children:
#                 return False
#             node = node.children[char]
#         return True

#     def remove(self, word):
#         self._remove(self.root, word, 0)

#     def _remove(self, node, word, index):
#         if index == len(word):
#             return not node.children
#         char = word[index]
#         if char not in node.children:
#             return False
#         shouldDeleteChild = self._remove(node.children[char], word, index + 1)
#         if shouldDeleteChild:
#             del node.children[char]
#             return not node.children
#         return False
    
#     def getBiggestCounterPart(self, numStr):
#         pointer = self.root
#         accumulatedStr = ''
#         for i in range(len(numStr)):
#             char = numStr[i]
#             # we always want to pick the opposite, if we have a 1 we pick a 0, if we have a 0 we pick a 1. if we have no option we proceed
#             if char == '1':
#                 if '0' in pointer.children:
#                     accumulatedStr += '1'
#                     pointer = pointer.children['0']
#                 else:
#                     accumulatedStr += '0'
#                     pointer = pointer.children['1']
#             elif char == '0':
#                 if '1' in pointer.children:
#                     accumulatedStr += '1'
#                     pointer = pointer.children['1']
#                 else:
#                     accumulatedStr += '0'
#                     pointer = pointer.children['0']
#         return int(accumulatedStr, 2)
                    
                    
                    
class BitTrie:
    def __init__(self, BITS=32):
        self.root = {}
        self.BITS = BITS

    def insert(self, num):
        curr = self.root
        for bitOffset in range(self.BITS - 1, -1, -1):
            bit = (num >> bitOffset) & 1
            if bit not in curr:
                curr[bit] = {}
            curr = curr[bit]
    
    def queryMaxXor(self, numToBeXord):
        res = 0
        curr = self.root
        if not curr:
            return None
        for bitOffset in range(self.BITS - 1, -1, -1):
            numBit = (numToBeXord >> bitOffset) & 1
            desiredBit = numBit ^ 1
            if desiredBit in curr:
                res |= (1 << bitOffset)
                curr = curr[desiredBit]
            else:
                curr = curr[numBit]
        return res

    def queryMinXor(self, numToBeXord):
        res = 0
        curr = self.root
        if not curr:
            return None
        for bitOffset in range(self.BITS - 1, -1, -1):
            numBit = (numToBeXord >> bitOffset) & 1
            if numBit in curr:
                curr = curr[numBit]
            else:
                res |= (1 << bitOffset)
                curr = curr[numBit ^ 1]
        return res

    def remove(self, num):
        curr = self.root
        stack = []

        # Traverse and store the nodes and bits in a stack
        for bitOffset in range(self.BITS - 1, -1, -1):
            bit = (num >> bitOffset) & 1
            if bit not in curr:
                return  # The number doesn't exist in the trie
            stack.append((curr, bit))
            curr = curr[bit]

        # Remove nodes starting from the leaf
        while stack:
            node, bit = stack.pop()
            del node[bit]
            if node:
                break  # Stop if the current node has other children


class Solution:
    def maximumStrongPairXor(self, nums: List[int]) -> int:
        nums = list(set(nums)) # remove duplicates
        
        # forces length 21
        def toStr(num):
            # print(f'to str called on num {num}, str is: {bin(num)[2:].zfill(21)}')
            return bin(num)[2:].zfill(21)
        
        nums.sort()
        trie = BitTrie(32)
        trie.insert(nums[0])
        
        res = 0
        l = 0 # a pointer to our smallest number, we increment as needed
        
        for i in range(1, len(nums)):
            newNum = nums[i]
            while nums[l] < newNum / 2:
                lostNum = nums[l]
                lostNumStr = toStr(lostNum)
                trie.remove(lostNum)
                l += 1
                
                
            newNumStr = toStr(newNum)
            trie.insert(newNum)
            biggestCounterpart = trie.queryMaxXor(newNum)
            res = max(res, biggestCounterpart)
            
        
        return res
        
64800