Max XOR (Bit Trie)
Store numbers as 32-bit binary strings in a trie (each node has children 0 and 1). To find the max XOR for a number, greedily choose the opposite bit at each level (1 if you have 0, 0 if you have 1). This maximizes each bit position.
How It Works
A binary trie stores each number as its 32-bit path from the most significant bit down, every node having at most two children (0 and 1). To find which stored number maximizes XOR with a query value, walk from the root and at each bit greedily take the child opposite to the query's bit — an opposite bit contributes a 1 to that XOR position. If the opposite child is missing, settle for the same-bit child and continue.
The greedy is safe because bit positions are independent and higher bits dominate: securing a 1 at bit k outweighs every possible gain from bits below it combined. Each insertion and each query costs O(32) = O(1) per number, so Maximum XOR over n numbers runs in O(32n), replacing the O(n^2) all-pairs comparison. The same structure answers online queries with constraints, as in Maximum XOR With an Element From Array.
Step-by-Step Visualization
Code
static int findMaxXOR(int[] nums) {
Map<Integer, Map<Integer, Object>> trie = new HashMap<>();
int max = 0;
for (int num : nums) {
// Insert num into bit trie
Map<Integer, Object> node = trie.computeIfAbsent(0, k -> new HashMap<>());
for (int i = 31; i >= 0; i--) {
int bit = (num >> i) & 1;
node = (Map<Integer, Object>) ((Map)node).computeIfAbsent(bit, k -> new HashMap<>());
}
// Query for max XOR
node = (Map<Integer, Object>) trie.get(0);
int xor = 0;
for (int i = 31; i >= 0; i--) {
int bit = (num >> i) & 1;
int want = 1 - bit;
if (((Map)node).containsKey(want)) { xor |= (1 << i); node = (Map)((Map)node).get(want); }
else node = (Map)((Map)node).get(bit);
}
max = Math.max(max, xor);
}
return max;
}Tips & Gotchas
Practice Problems
- 1Maximum XOR of Two Numbers in an Array
- 2Maximum XOR With an Element From Array
- 3Count Pairs With XOR in a Range
About the Advanced Trie Pattern
Extend the basic trie to handle wildcards, combine with DFS for grid search, or store binary representations of numbers for XOR optimization.
Use a trie when you need prefix-based operations that hash maps can't do efficiently — like 'find all words starting with X' or 'find word matching pattern with wildcards'.
Common Trie Interview Problems
- Implement Trie
- Word Search II
- Design Add and Search Words
- Replace Words
- Maximum XOR of Two Numbers
Frequently Asked Questions
Why is greedily choosing the opposite bit at each level correct?
The XOR contribution of bit k is 2^k, which strictly exceeds the sum of all lower bit contributions (2^k > 2^(k-1) + ... + 1). Locking in a mismatch at a high bit therefore beats any combination of wins at lower bits, so the top-down greedy can never be improved by backtracking.
How does the bit trie compare to the hash-set prefix method for Maximum XOR?
Both run in O(32n). The hash method iterates bit positions, guessing each answer bit and verifying with set lookups; the trie makes one pass per query with simpler reasoning and extends naturally to online insertion, deletion (with node counts), and value-limited queries, at the cost of more memory for nodes.
How do I support deletions from a binary trie?
Store a pass-through counter on every node, incremented on insert and decremented on delete. During queries, treat a child with count zero as absent. This keeps all operations O(32) without physically freeing nodes.