Prefix Tree Thinking Process
Intuitively, \n\nfor i 0 .. n\n  for j i+1 .. n\n    overallMax = max(overallMall, nums[i] ^ nums[j])\n\n> That takes O(n^2) time.\n\n> However, O(n) time is re
>Intuitively, \n```\nfor i 0 .. n\n  for j i+1 .. n\n    overallMax = max(overallMall, nums[i] ^ nums[j])\n```\n> That takes O(n^2) time.\n\n> However, O(n) time is required. \n> \n> In other words, we have to enable nums[i] to know **which element paired with itself can form the maximum XOR**. Then we calculate the maximum XOR for each num and aggregate the overall maximum.\n\n\n> Given nums[i], how does the target element (paired with nums[i] that makes the maximum XOR) look like?\nThe target element should share shortest common prefixes  with nums[i].\n\n> How do we tell which element shares the shortest common prefixes with nums[i]?\n> Prefix tree\n\n> What is a node in the prefix tree?\n> zero means the bit is not set\n> one means the bit is set\n> the height of a node indicates which bit it is\n\n```\nclass Solution {\n    private Node root;\n    \n    public int findMaximumXOR(int[] nums) {\n        root = new Node();\n        \n        // Build a trie from nums\n        for (int num : nums) {\n            insert(num);\n        }\n        \n        int overallMax = Integer.MIN_VALUE;\n        // Search for num in the trie, and get its maximum XOR to update the overal maximum\n        for (int num : nums) {\n            overallMax = Math.max(overallMax, search(num));\n        }\n        \n        return overallMax;        \n    }\n    \n    private void insert(int num) {\n        Node ptr = root;\n        // i indicates bit position for the rightmost bit is at position 0\n        // i also indicates node\'s depth in trie, i.e. the length of the path from root to the end\n        for (int i = 31; i >= 0; i--) {\n            int val = (num >> i) & 1;\n            if (val == 1) {\n                if (ptr.one == null) {\n                    ptr.one = new Node();\n                }\n                ptr = ptr.one;\n            } else {\n                if (ptr.zero == null) {\n                    ptr.zero = new Node();\n                }\n                ptr = ptr.zero;\n            }\n        }\n    }\n    \n    private int search(int num) {\n        Node ptr = root;\n        int maxXOR = 0;\n        for (int i = 31; i >= 0; i--) {\n            int val = (num >> i) & 1;\n            if (val == 1) {\n                if (ptr.zero != null) {\n                    ptr = ptr.zero;\n                    maxXOR += (1 << i);\n                } else {\n                    ptr = ptr.one;\n                }\n            } else {\n                if (ptr.one != null) {\n                    ptr = ptr.one;\n                    maxXOR += (1 << i);\n                } else {\n                    ptr = ptr.zero;\n                }\n            }\n        }\n        return maxXOR;\n    }\n    \n    class Node {\n        Node zero;\n        Node one;\n    }\n}\n```
[]