LeetCode 421: Maximum XOR of Two Numbers in an Array Solution

Master LeetCode problem 421 (Maximum XOR of Two Numbers in an Array), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

421. Maximum XOR of Two Numbers in an Array

Medium

Array Hash Table Bit Manipulation Trie

Problem Explanation

Explanation

To solve this problem, we can use a bitwise trie (prefix tree) to find the maximum XOR value between any two numbers in the given array. We iterate from the most significant bit to the least significant bit for each number in the array. At each step, we check if there exists a bit that, when XORed with the current prefix, will give a maximum result. If such a bit exists, we update the answer with the new result. We build the trie based on the binary representation of the numbers in the array.

Time complexity: O(n), where n is the number of elements in the array. Space complexity: O(n).

Solution Code

class TrieNode {
    TrieNode[] children;

    public TrieNode() {
        children = new TrieNode[2];
    }
}

class Solution {
    public int findMaximumXOR(int[] nums) {
        TrieNode root = new TrieNode();
        int maxXor = 0;

        for (int num : nums) {
            TrieNode currNode = root, xorNode = root;
            int currXor = 0;

            for (int i = 31; i >= 0; i--) {
                int bit = (num >>> i) & 1;
                if (currNode.children[bit] == null) {
                    currNode.children[bit] = new TrieNode();
                }
                currNode = currNode.children[bit];

                int flipBit = 1 - bit;
                if (xorNode.children[flipBit] != null) {
                    currXor |= (1 << i);
                    xorNode = xorNode.children[flipBit];
                } else {
                    xorNode = xorNode.children[bit];
                }
            }

            maxXor = Math.max(maxXor, currXor);
        }

        return maxXor;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 421 (Maximum XOR of Two Numbers in an Array)?

This page provides optimized solutions for LeetCode problem 421 (Maximum XOR of Two Numbers in an Array) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 421 (Maximum XOR of Two Numbers in an Array)?

The time complexity for LeetCode 421 (Maximum XOR of Two Numbers in an Array) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 421 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 421 in Java, C++, or Python.

Back to LeetCode Solutions