Trie - Question 1

 Leetcode 421 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.

Constraints:

1 <= nums.length <= 2 * 10^5

0 <= nums[i] <= 2^31 - 1

Analysis:

The naïve method is to use a two-layer for loop, to check every pair of numbers. The total time complexity is O(N^2), which  is too large since N could be 2*10^5.

There are methods to using the bit-wise operations directly, which will be discussed in the Bit Manipulation post. Here we will focus on the method using trie.

The key ideas are:

1. for each number, there are 32 bits. For each bit, only two possible values are available; thus we can build a binary trie to store all the numbers;

2. once the trie is built (the height is 32), we can iterate array, for each number we can check its 32 bits along with the trie layer by layer (32 layers). If the bit for the number is 1, we want to find the node with a bit value of 0 (why?  because we are search for 'exclusive or', and 1^0 gives 1. If the node does not exist, then this bit has to be 0. Similar argument can be applied to the case that the bit value is 0.

3. since we are looking for maximum, we need to start with the most significant bit.

4. since all the numbers' bits are stored in the trie,  for each number, we just need to check 32 bits of the number vs 32 layer of the trie. Or in 32 steps, we can obtain the maximum xor results between the current number with all the numbers in the array. Thus, the overall time complexity is O(32*N). 

See the code bleow:

class Solution {
struct node {
    vector<node*> ns;
    node() {
        ns.resize(2);
    }
};
public:
    int findMaximumXOR(vector<int>& nums) {
        node* root = new node();
        buildTree(root, nums);
        int res = INT_MIN;
        for(auto &a : nums) {
            res = max(res, findMax(a, root));
        }
        return res;
    }
private:
    void buildTree(node* root, vector<int>& nums) {
        for(auto &a : nums) {
            node* p = root;
            for(int i=31; i>=0; --i) {
                if(a>>i & 1) {
                    if(!p->ns[1]) p->ns[1] = new node();
                    p = p->ns[1];
                }
                else {
                    if(!p->ns[0]) p->ns[0] = new node();
                    p = p->ns[0];
                }
            }
        }
    }
    int findMax(int val, node* root) {
        int res = 0;
        node* p = root;
        for(int i=31; i>=0; --i) {
            if(val>>i & 1) {
                if(p->ns[0]) {
                    res |= 1<<i;
                    p = p->ns[0];
                }
                else p = p->ns[1];
            }
            else {
                if(p->ns[1]) {
                    res |= 1<<i;
                    p = p->ns[1];
                }
                else p = p->ns[0];
            }
        }
        return res;
    }
};

Upper Layer