Maximum XOR of Two Numbers in an Array (LeetCode 421)

The problem

You get an array of non-negative integers. Return the largest value of nums[i] XOR nums[j] over all pairs (i may equal j, which gives 0).

Input:  [3, 10, 5, 25, 2, 8]
Output: 28

5 XOR 25 is 00101 XOR 11001 = 11100, which is 28. No other pair beats it.

How to think about it

Start with brute force. Try every pair and keep the maximum XOR. That is O(n²). With up to 2·10⁵ numbers, that is about 2·10¹⁰ operations, far too slow.

The key insight: the highest bit decides everything. A 1 in bit 4 (worth 16) beats any combination of the lower bits (at most 15). So for a fixed number, the best partner is the one that differs from it in the highest possible bit, then, among those, in the next highest, and so on. That is a greedy choice bit by bit from the top.

A trie makes the greedy choice cheap. Insert every number as a 32-step path of bits, from bit 31 down to bit 0. Now, for a number num, walk down from the root. At each bit b, try to go to the child 1 - b: if it exists, some stored number differs here, so this bit of the XOR is 1. If it does not exist, you are forced to follow b and this bit is 0. After 32 steps you have the best XOR for num, in O(32).

Which pattern is this? A trie where the alphabet is {0, 1}, the “storing numbers bit by bit” case from the lesson. The tell is “maximum XOR” over pairs.

Approach

1. Build a bit trie: for each number, walk bits 31 down to 0, creating child 0 or 1 as needed.
2. For each number, start at the root with cur = 0.
3. At each bit i, let b be the number’s bit and want = 1 - b.
4. If want is a child, set bit i of cur and go there. Otherwise go to b.
5. Track the maximum cur across all numbers and return it.

Solution

def findMaximumXOR(nums):
    root = {}
    for num in nums:
        n = root
        for i in range(31, -1, -1):
            b = (num >> i) & 1; n = n.setdefault(b, {})   # insert bit path
    best = 0
    for num in nums:
        n = root; cur = 0
        for i in range(31, -1, -1):
            b = (num >> i) & 1; want = 1 - b               # opposite bit gives a 1
            if want in n: cur |= (1 << i); n = n[want]
            else:         n = n[b]                         # forced: this XOR bit is 0
        best = max(best, cur)
    return best
# findMaximumXOR([3,10,5,25,2,8]) -> 28

Dry run

The walk for num = 5 (00101) over the low five bits (bits 31 to 5 are 0 for every number, so the walk just follows 0 there):

Across all numbers, cur comes out as 26, 19, 28, 28, 27, 17 for 3, 10, 5, 25, 2, 8, so best is 28.

Complexity

• Time: O(32·n), effectively O(n). Each number is inserted with 32 steps and queried with 32 steps.
• Space: O(32·n) trie nodes in the worst case, when numbers share few leading bits.

Edge cases and pitfalls

• One number returns 0, because a number XOR itself is 0.
• Duplicates ([7, 7]) give 0 too; they share a path.
• Walk from the high bit down. Going from bit 0 up makes the greedy choice meaningless.
• Fixed width. Every number must use the same number of levels (32 here), or paths are not comparable.
• Negative numbers are not in this problem; Python’s >> on negatives would need masking.

Related problems

• Single Number (LeetCode 136): the core XOR facts, without the trie.
• Implement Trie (Prefix Tree) (LeetCode 208): the same structure over letters instead of bits.
• Counting Bits (LeetCode 338): more practice reading numbers bit by bit.