Trie Data Structure || O(N) solution🔥
Approach and Intuition:\n\nThis solution revolves around using a Trie (prefix tree) to efficiently find the maximum XOR value for a given array of integers. The
### Approach and Intuition:\n\nThis solution revolves around using a **Trie** (prefix tree) to efficiently find the maximum XOR value for a given array of integers. The idea behind the Trie structure is to insert the binary representations of the integers in the array and use it to maximize the XOR for each number by greedily choosing bits that will contribute the most to the XOR result.\n\n#### Steps:\n1. **Inserting Numbers into the Trie**:\n   Each number is inserted into the Trie as a 32-bit binary number (assuming 32-bit integers). During the insertion, each bit of the number is inserted into the Trie, starting from the most significant bit (bit 31). This ensures that the numbers are stored in the Trie in their binary form.\n\n2. **Finding Maximum XOR**:\n   For each number in the array, the goal is to find the number in the Trie that produces the largest XOR with the current number. The algorithm works by traversing the Trie bit by bit:\n   - For each bit in the current number, it checks if the opposite bit is present in the Trie (i.e., if the current bit is 0, it checks if 1 is present, and vice versa). This is because XORing opposite bits yields a `1`, which maximizes the XOR.\n   - If the opposite bit is present, the algorithm chooses that path and adds a `1` to the XOR result at the corresponding position. Otherwise, it follows the same bit and continues to the next position.\n\n#### Key Intuition:\n- XOR is maximized when different bits are compared. Therefore, the goal is to choose the path in the Trie that gives the most number of `1`s in the XOR result, bit by bit.\n- By using a Trie, we can efficiently store and search for binary numbers in logarithmic time relative to the bit length of the numbers (32 bits in this case), making the solution much faster than a brute-force approach.\n\n### Time Complexity:\n\n1. **Inserting a number into the Trie**:\n   - Each number is 32 bits long. For each bit, you either traverse or create a node in the Trie.\n   - **Time Complexity for each insertion**: O(32) = O(1) (constant time per insertion).\n   - Since there are `n` numbers in the array, the total time complexity for inserting all numbers is O(32 * n) = O(n).\n\n2. **Finding the maximum XOR**:\n   - For each number, you traverse the Trie to find the number that gives the maximum XOR. This again requires traversing 32 levels in the Trie.\n   - **Time Complexity for each query**: O(32) = O(1) (constant time per query).\n   - Since you perform this query for each number in the array, the total time complexity for this step is O(32 * n) = O(n).\n\n### Overall Time Complexity:\n- **Inserting all numbers + finding maximum XOR**: O(n) for inserting + O(n) for querying = O(n) total time complexity.\n- This is highly efficient compared to a brute-force approach, which would take O(n^2) for pairwise comparisons.\n\n### Space Complexity:\n- Each node in the Trie has two possible children (`links[0]` and `links[1]`), so in the worst case, the Trie could have up to `n * 32` nodes, where `n` is the number of integers and 32 is the number of bits.\n- **Space Complexity**: O(n * 32) = O(n).\n\n### Summary of Approach:\n1. Insert all numbers into a Trie in their 32-bit binary form.\n2. For each number in the array, find the number in the Trie that gives the maximum XOR result with the current number.\n3. Use the XOR property and greedy traversal of the Trie to maximize the XOR result bit by bit.\n\nThis approach is efficient with a time complexity of **O(n)** and avoids the pitfalls of a brute-force O(n^2) solution.\n\n# Code\n```java []\n// Time Complexity - : O(32*n)\n// Space Complexity - : O(32*n)\nclass Node{\n    Node[] links = new Node[2];\n    Node(){}\n    public boolean containsKey(int bit){\n        return links[bit]!=null;\n    }\n    public void put(int bit,Node node){\n        links[bit]=node;\n    }\n    public Node get(int bit){\n        return links[bit];\n    }\n}\npublic class Trie{\n\n    private static Node root;\n\n    public Trie(){\n        root = new Node();\n    }\n\n    public static  void insert(int num){\n        Node node = root;\n        for(int i=31;i>=0;i--){\n            int bit = ((num>>i) & 1);\n            if(!node.containsKey(bit)){\n                node.put(bit,new Node());\n            }\n            node = node.get(bit);\n        }\n    }\n\n    public  static int find_max(int num){\n        int maxi=0;\n        Node node = root;\n        for(int i=31;i>=0;i--){\n            int bit = ((num>>i) & 1);\n            if(node.containsKey(1-bit)){\n                maxi = (maxi | (1<<i));\n                node = node.get(1-bit);\n            }\n            else{\n                node = node.get(bit);\n            }\n        }\n        return maxi;\n    }\n}\nclass Solution {\n    public int findMaximumXOR(int[] nums) {\n\n        Trie trie = new Trie();\n        for(int i=0;i<nums.length;i++){\n            trie.insert(nums[i]);\n        }\n\n        int answer=0;\n        for(int i=0;i<nums.length;i++){\n\n            answer = Math.max(answer,trie.find_max(nums[i]));\n        }\n\n        return answer;\n        \n    }\n}\n```
['Trie', 'Java']