Maximum XOR of Two Numbers in an Array

I had this on a Two Sigma onsite during the algorithms round, after Two Sum and before merge intervals. The brute-force O(n^2) is fine to mention, but the interviewer asked for O(n * 32), which is the bit-trie approach. The trick is greedy: at every level of the trie, you try to take the OPPOSITE bit of the current number, because that's what maximizes XOR.

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.

Examples

Example 1:

• Input: nums = [3, 10, 5, 25, 2, 8]
• Output: 28
• Explanation: 5 XOR 25 = 28. In binary: 00101 XOR 11001 = 11100.

Example 2:

• Input: nums = [0]
• Output: 0
• Explanation: The only pair is (0, 0) and 0 XOR 0 == 0.

Example 3:

• Input: nums = [2, 4]
• Output: 6
• Explanation: 2 XOR 4 = 6. In binary: 010 XOR 100 = 110.

Example 4:

• Input: nums = [8, 10, 2]
• Output: 10
• Explanation: 8 XOR 2 = 10. In binary: 1000 XOR 0010 = 1010.

Constraints

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

Follow-up

Can you do better than O(n^2)? Yes, using a binary trie of bits, the answer is O(n * 32). At each bit from high to low, the greedy choice is to descend toward the OPPOSITE bit of the current number when that branch exists; that maximizes the XOR.