Maximum XOR of Two Numbers in an Array
Pick two numbers from the array maximizing a XOR b — in better than O(n²).
- 1 <= nums.length <= 2 * 10⁵
- 0 <= nums[i] <= 2³¹ - 1
Intuition
Maximum xor of two numbers in an array asks for the largest a XOR b over all pairs. Checking every pair is O(n²), and beating that requires a way to find, for a given number, its best possible partner without examining all the others.
The property to exploit is how XOR is built. A bit contributes to the result only when the two numbers differ there, and a single high bit outweighs every lower bit combined — bit 30 alone is worth more than bits 0 through 29 together. So maximising the XOR means greedily securing the highest bits first, in order, and never trading a high bit for any number of low ones.
That greedy order is what a binary trie indexes. Insert every number as a path of bits from most significant to least, so at each level the trie splits the numbers by their bit at that position.
Now the best partner for a number falls out of a walk:
- At each bit, take the branch holding the opposite bit if it exists, since a differing bit sets that XOR bit to 1.
If the opposite branch is empty, take the same-bit branch — that bit contributes nothing, but no better option exists at this level and the choice cannot be revisited.
Thirty-two steps per number, n numbers, so the whole thing is linear in the number count with a constant factor of the bit width. The trie is also what the constrained variant builds on, where an offline sweep controls which numbers are present.
A bitwise trie over 32-bit numbers. XOR is maximised bit by bit from the top: at each level, greedily follow the opposite bit if that branch exists, because setting a high bit outweighs everything below it. Storing numbers as bit-paths is what makes "is there a number with the opposite bit here?" an O(1) lookup.
Approach
Before reading on: price up what the brute force costs here, then ask what the shared prefixes let you avoid storing twice. Aim for O(32n) time and O(32n) space.
Reason bit by bit from the top
A differing bit at position k contributes 2^k, which exceeds the sum of everything below it. So securing a high bit is always worth more than any combination of lower bits, which is what makes the greedy walk correct rather than merely plausible.
Insert numbers as bit paths
Build a trie where each node has children for bit 0 and bit 1, and each number is a path from the most significant bit down. Most-significant-first is essential — the greedy walk depends on deciding high bits before low ones.
Pad to a fixed bit width
Insert every number using the same number of bits, typically 31 or 32. Without padding, numbers of different magnitudes take paths of different lengths and cannot be compared level by level.
Walk preferring the opposite bit
For each number, descend the trie taking the child whose bit differs from the current bit, since that sets this XOR bit to 1. Accumulate the result as you go, shifting left and adding the bit obtained.
Fall back when the branch is missing
If the opposite branch is empty, take the same-bit child — that position contributes 0. There is no backtracking: the greedy choice at a higher bit is never worth revisiting for a lower one.
Track the maximum across all numbers
Run the query for every number and keep the largest XOR found. Each number acts as one side of the pair, and its best partner is found in a single descent.
Cost of the trie approach
Insertion and querying are both O(32) per number, giving O(32n) time — linear in n — and O(32n) space for the trie nodes. Compare with O(n²) for checking every pair.
Solution & live demo
Common pitfalls
Comparing every pair
return max(a ^ b for a in nums for b in nums)
for i in range(31, -1, -1):
want = 1 - b
if want in cur: ...O(n²) times out at n = 200,000. The trie answers "what is the best partner for this number?" in 32 steps regardless of how many numbers there are.
Iterating bits from least significant upward
for i in range(32):
for i in range(31, -1, -1):
The greedy only works top-down: securing bit 30 is worth more than every lower bit combined. Starting from the bottom makes early choices that a later high bit can't justify.
Not falling back when the opposite branch is missing
if want in cur:
xor_val |= (1 << i); cur = cur[want]if want in cur:
xor_val |= (1 << i); cur = cur[want]
elif b in cur:
cur = cur[b]If no stored number has the opposite bit, the walk must continue down the same-bit branch — that bit simply contributes 0. Without the fallback cur goes stale and every deeper comparison is meaningless.
Edge cases
Opposite branch never exists — XOR 0.
Pairs with itself → 0 (insert-then-query order makes this safe).
Zero's best partner is simply the max element.