Maximum XOR of Two Numbers in an Array
Find the maximum XOR of any two numbers in an array by storing every number's bits in a trie and greedily walking toward the opposite bit at each level.
Problem Understanding
Maximum XOR of Two Numbers in an Array (LeetCode 421): given non-negative integers nums, return the maximum value of nums[i] XOR nums[j] over all pairs.
Examples: [3,10,5,25,2,8] → 28 (5 XOR 25); [14,70,53,83,49,91,36,80,92,51,66,70] → 127.
The Intuition: Win the Highest Bit First
Checking every pair is O(n²). A trie of bits answers "what is the best partner for this number?" in one pass down:
- Store bits, highest first. Each path from the root to a leaf is one number.
- Walk against your own bits. At each level, prefer the child with the opposite bit; that bit of the XOR becomes 1.
- Fall back only when forced. If the opposite child is missing, the same bit is the only way on, and that XOR bit is 0.
The same trie mechanics are built from scratch in Implement Trie, and XOR's cancelling behaviour is the core of Single Number.
Interactive Walkthrough
ONE NODE PER BIT, HIGHEST FIRST · NUMBER ABOVE A LEAF
BUILD THE TRIE
number
:
xor so far
:
best
0
6 numbers, written in 5 bits. First, every number goes into a trie of its bits
Next
Insert 3 = 00011: one node per bit, highest bit first
nums
The trie fills first, one number at a time. Then each number walks it, taking the opposite bit wherever it can; the leaf it reaches is its best partner. Try Spread out, where one pair differs in every bit.
Dry Run Table
Input: [3,10,5,25,2,8], 5 bits.
| Number | Best partner | XOR |
|---|---|---|
| 3 (00011) | 25 | 26 |
| 10 (01010) | 25 | 19 |
| 5 (00101) | 25 | 28 |
| 25 (11001) | 5 | 28 |
| 2 (00010) | 25 | 27 |
| 8 (01000) | 25 | 17 |
Answer: 28.
The Solution Template
Build the bit trie, then one greedy walk per number.
Maximum XOR of Two Numbers in an Array Code
1var findMaximumXOR = function(nums) {2 const bits = Math.max(Math.max(...nums).toString(2).length, 1);3 const root = {};4 for (const v of nums) {5 let node = root;6 for (let k = bits - 1; k >= 0; k--) {7 const b = (v >> k) & 1;8 node = node[b] ??= {};9 }10 }11 let best = 0;12 for (const v of nums) {13 let node = root, x = 0;14 for (let k = bits - 1; k >= 0; k--) {15 const b = (v >> k) & 1;16 if (node[1 - b]) {17 x |= 1 << k;18 node = node[1 - b];19 } else {20 node = node[b];21 }22 }23 best = Math.max(best, x);24 }25 return best;26};
Edge Cases & Common Mistakes
- One number: its only pair is itself, so the answer is 0.
- All numbers equal: every walk is forced, answer 0.
- Inserting low bits first: the greedy choice must start at the most significant bit.
- Querying before inserting everything: fine if you insert then query each number in turn, but the partner must already be in the trie.
- Zero values: bit length of 0 is 0; use at least one bit.
Summary
Insert every number into a binary trie, highest bit first; for each number walk toward the opposite bit whenever possible. The largest XOR built by any walk is the answer. O(n · B) time and space.
More practice: DSA interview questions with answers · patterns cheat sheet