Description Link to heading
421. Maximum XOR of Two Numbers in an Array (Medium)
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⁵0 <= nums[i] <= 2³¹ - 1
Solution Link to heading
If we directly use a brute-force approach to find the maximum XOR value, the time complexity would be $O(n^2)$, which would inevitably lead to timeout errors.
In reality, we can view the binary representation of each number as a string. Therefore, we can optimize the process of finding the XOR value by utilizing a data structure called a trie. In the brute-force scenario, when calculating the XOR value of nums[i] with other values, we need to traverse the entire array, resulting in a time complexity of $O(n)$. However, by using a trie, we can reduce this comparison time complexity from $O(n)$ to $O(\log_2C)$, where $C$ represents the magnitude of the numbers and $\log_2C$ corresponds to the number of bits in the binary representation of the numbers.
To find the maximum XOR value, we should compare the numbers starting from the highest bit. Therefore, the trie should be constructed from the most significant bit. Since 0 <= nums[i] <= 2^31 - 1, we can insert the result of right-shifting nums[i] by j bits into the trie, with j decreasing from $31$ to $0$.