<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>

class TrieNode:
  def __init__(self):
    self.children: list[TrieNode | None] = [None] * 2
    self.mn = math.inf
    self.mx = -math.inf


class BitTrie:
  def __init__(self, maxBit: int):
    self.maxBit = maxBit
    self.root = TrieNode()

  def insert(self, num: int) -> None:
    node = self.root
    for i in range(self.maxBit, -1, -1):
      bit = num >> i & 1
      if not node.children[bit]:
        node.children[bit] = TrieNode()
      node = node.children[bit]
      node.mn = min(node.mn, num)
      node.mx = max(node.mx, num)

  def getMaxXor(self, x: int) -> int:
    """Returns max(x ^ y) where |x - y| <= min(x, y).

    If x <= y, |x - y| <= min(x, y) can be written as y - x <= x.
    So, y <= 2 * x.
    """
    maxXor = 0
    node = self.root
    for i in range(self.maxBit, -1, -1):
      bit = x >> i & 1
      toggleBit = bit ^ 1
      # If `node.children[toggleBit].mx > x`, it means there's a number in the
      # node that satisfies the condition to ensure that x <= y among x and y.
      # If `node.children[toggleBit].mn <= 2 * x`, it means there's a number in
      # the node that satisfies the condition for a valid y.
      if (node.children[toggleBit] and
          node.children[toggleBit].mx > x and
              node.children[toggleBit].mn <= 2 * x):
        maxXor = maxXor | 1 << i
        node = node.children[toggleBit]
      elif node.children[bit]:
        node = node.children[bit]
      else:  # There's nothing in the Bit Trie.
        return 0
    return maxXor


class Solution:
  # Same as 2932. Maximum Strong Pair XOR I
  def maximumStrongPairXor(self, nums: list[int]) -> int:
    maxNum = max(nums)
    maxBit = int(math.log2(maxNum))
    bitTrie = BitTrie(maxBit)

    for num in nums:
      bitTrie.insert(num)

    return max(bitTrie.getMaxXor(num) for num in nums)
73500