Code Implementation

class TrieNode:
    def __init__(self):
        self.children = {}
        
class Solution:
    def findMaximumXOR(self, nums):
        # Build Trie
        root = TrieNode()
        for num in nums:
            node = root
            for i in range(31, -1, -1):  # 32 bits for int
                bit = (num >> i) & 1
                if bit not in node.children:
                    node.children[bit] = TrieNode()
                node = node.children[bit]
        
        max_xor = 0
        for num in nums:
            node = root
            curr_xor = 0
            for i in range(31, -1, -1):
                bit = (num >> i) & 1
                toggled_bit = 1 - bit
                if toggled_bit in node.children:
                    curr_xor |= (1 << i)
                    node = node.children[toggled_bit]
                else:
                    node = node.children.get(bit)
            max_xor = max(max_xor, curr_xor)
        return max_xor
      

class TrieNode {
public:
    TrieNode* children[2];
    TrieNode() {
        children[0] = children[1] = nullptr;
    }
};

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        TrieNode* root = new TrieNode();
        // Build Trie
        for (int num : nums) {
            TrieNode* node = root;
            for (int i = 31; i >= 0; --i) {
                int bit = (num >> i) & 1;
                if (!node->children[bit])
                    node->children[bit] = new TrieNode();
                node = node->children[bit];
            }
        }
        int max_xor = 0;
        for (int num : nums) {
            TrieNode* node = root;
            int curr_xor = 0;
            for (int i = 31; i >= 0; --i) {
                int bit = (num >> i) & 1;
                int toggled = 1 - bit;
                if (node->children[toggled]) {
                    curr_xor |= (1 << i);
                    node = node->children[toggled];
                } else {
                    node = node->children[bit];
                }
            }
            max_xor = max(max_xor, curr_xor);
        }
        return max_xor;
    }
};
      

class TrieNode {
    TrieNode[] children = new TrieNode[2];
}

class Solution {
    public int findMaximumXOR(int[] nums) {
        TrieNode root = new TrieNode();
        // Build Trie
        for (int num : nums) {
            TrieNode node = root;
            for (int i = 31; i >= 0; --i) {
                int bit = (num >> i) & 1;
                if (node.children[bit] == null) {
                    node.children[bit] = new TrieNode();
                }
                node = node.children[bit];
            }
        }
        int maxXor = 0;
        for (int num : nums) {
            TrieNode node = root;
            int currXor = 0;
            for (int i = 31; i >= 0; --i) {
                int bit = (num >> i) & 1;
                int toggled = 1 - bit;
                if (node.children[toggled] != null) {
                    currXor |= (1 << i);
                    node = node.children[toggled];
                } else {
                    node = node.children[bit];
                }
            }
            maxXor = Math.max(maxXor, currXor);
        }
        return maxXor;
    }
}
      

class TrieNode {
    constructor() {
        this.children = {};
    }
}

var findMaximumXOR = function(nums) {
    let root = new TrieNode();
    // Build Trie
    for (let num of nums) {
        let node = root;
        for (let i = 31; i >= 0; --i) {
            let bit = (num >> i) & 1;
            if (!(bit in node.children)) {
                node.children[bit] = new TrieNode();
            }
            node = node.children[bit];
        }
    }
    let maxXor = 0;
    for (let num of nums) {
        let node = root;
        let currXor = 0;
        for (let i = 31; i >= 0; --i) {
            let bit = (num >> i) & 1;
            let toggled = 1 - bit;
            if (toggled in node.children) {
                currXor |= (1 << i);
                node = node.children[toggled];
            } else {
                node = node.children[bit];
            }
        }
        maxXor = Math.max(maxXor, currXor);
    }
    return maxXor;
};
      

Problem Description

Given an array of non-negative integers nums, your task is to find the maximum result of nums[i] XOR nums[j], where 0 ≤ i < j < nums.length. In other words, you want to pick two different elements from the array and compute their bitwise XOR, and among all possible pairs, return the largest value you can obtain.

• You must not use the same element twice (i.e., i ≠ j).
• The array can have up to 2 × 10⁵ elements.
• Each element is a non-negative integer less than 2³¹.
• There is always at least one valid pair.

Thought Process

At first glance, the problem seems to ask for the largest XOR value possible by picking any two numbers from the list. The most direct (brute-force) approach would be to try every possible pair, calculate their XOR, and keep track of the maximum. But with potentially hundreds of thousands of elements, this would require billions of calculations, which is far too slow.

To optimize, we need to exploit properties of the XOR operation. XOR tends to be maximized when the two numbers are as different as possible in their binary representations—ideally, when their bits differ as much as possible, especially in the higher (more significant) bits. This suggests that we should look for pairs that differ in the leftmost bits first.

Instead of comparing every pair, we can use a data structure that helps us quickly find, for each number, another number in the array that would maximize the XOR value with it. This is where a Trie (prefix tree) comes in handy: it can help us efficiently search for the "best partner" for each number, bit by bit.

Solution Approach

• 1. Build a Trie: First, insert all numbers from the array into a binary Trie. Each node in the Trie represents a bit (0 or 1) at a certain position (from the highest bit to the lowest).
• 2. For each number, find its best XOR partner: For every number in the array, traverse the Trie from the highest to lowest bit. At each bit, try to go the opposite direction (i.e., if the current bit is 0, try to go to 1, and vice versa). This is because XOR is maximized when bits differ.
• 3. Calculate the XOR: As you traverse, keep track of the current XOR value being formed. If you can go the opposite direction at a bit, set that bit in the result; otherwise, go the same direction.
• 4. Track the maximum: After checking all numbers, return the largest XOR value found.

The Trie enables us to find the number that differs the most at each bit position in O(1) time per bit, which is much faster than checking every pair.

Example Walkthrough

Let's use nums = [3, 10, 5, 25, 2, 8] as an example.

1. Build the Trie: Insert each number's 32-bit binary representation into the Trie.
2. Check each number: For example, for num = 5 (binary 000...0101):
   • Start from the highest bit. At each bit position, try to go to the child node that represents the opposite bit (since XOR is maximized when bits differ).
   • Suppose at the 3rd bit from the right, 5 has a 1. Try to go to a 0 in the Trie at this position.
   • Continue this process for all bits, building up the XOR value as you go.
3. Find the best: For 5, the best partner is 25, since 5 ^ 25 = 28. Repeat for all numbers, and the overall maximum is 5 ^ 25 = 28.

By using the Trie, we efficiently find the best partner for each number without checking every possible pair.

Time and Space Complexity

• Brute-force approach:
  • Time: O(n²), since you check every pair.
  • Space: O(1), only need to store the maximum.
• Optimized Trie approach:
  • Time: O(n * L), where L is the number of bits (usually 32 for integers). For each number, you insert and search in the Trie, each taking O(L).
  • Space: O(n * L), since in the worst case, the Trie has up to n * L nodes (one path per number, each with L bits).

The optimized approach is much faster and easily handles large arrays.

Summary

To solve the "Maximum XOR of Two Numbers in an Array" problem efficiently, we leverage the properties of the XOR operation and use a binary Trie to quickly find, for each number, the "most different" number in the array. This approach reduces the problem from an unacceptably slow brute-force solution to a fast, scalable one. The key insight is that maximizing XOR means maximizing differences in higher-order bits, and the Trie lets us search for such differences efficiently.