LeetCode #421 Hard

Maximum XOR of Two Numbers in an Array

Pick two numbers from the array maximizing a XOR b — in better than O(n²).

triebit-manipulationgreedy

02

Intuition

💡

XOR is maximized bit by bit from the top: a high differing bit beats all lower bits combined. Store every number's 32-bit path in a binary trie (0/1 children). For each number, walk the trie greedily choosing the opposite bit whenever that branch exists — that partner maximizes the XOR with this number. Best over all numbers is the answer.

03

Approach

1

Why brute force wastes work

All pairs is O(n²). But the best partner for a number is determined greedily per bit — high bits dominate — so a per-bit index (the trie) finds it in 32 steps.

2

Build the bit trie

Insert each number as its 32-bit path, most significant bit first. Nodes are {0:…, 1:…} dicts.

3

Greedy opposite walk

For each num, from the top bit down: prefer the child with the flipped bit (sets this XOR bit to 1); fall back to the same bit. Accumulate the XOR value; track the global max.

04

Solution & live demo

python

▶1class Solution:
▶2    def findMaximumXOR(self, nums):
▶3        root, best = {}, 0
▶4        for num in nums:
▶5            node = cur = root
▶6            xor_val = 0
▶7            for i in range(31, -1, -1):
▶8                b = (num >> i) & 1
▶9                node = node.setdefault(b, {})       # insert path
▶10                want = 1 - b                        # greedy: opposite bit
▶11                if want in cur:
▶12                    xor_val |= (1 << i); cur = cur[want]
▶13                elif b in cur:
▶14                    cur = cur[b]
▶15            best = max(best, xor_val)
▶16        return best

05

Edge cases

All numbers equal

Opposite branch never exists — XOR 0.

Single element

Pairs with itself → 0 (insert-then-query order makes this safe).

Zero in the array

Zero's best partner is simply the max element.

06

Complexity

Time

O(32n)

Space

O(32n)

One insert + one greedy query per number.