Binary trie for maximum XOR

40 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

XOR (written ⊕) compares two numbers bit by bit and writes 1 where the bits differ. For example 5 ⊕ 2 is 101 ⊕ 010 = 111 = 7. Given the numbers [5, 2, 7, 3] (the video uses these four; the problem's full example has six), which pair has the largest XOR?

By hand you would compute every pair: 5⊕2 = 7, 5⊕7 = 2, 5⊕3 = 6, 2⊕7 = 5, 2⊕3 = 1, 7⊕3 = 4. The best is 7. Four numbers give 6 pairs; 100,000 numbers give about 5 billion pairs, too many.

Build the structure, one piece at a time

The insight is that XOR is decided from the top bit down. Among all partners, the one that gives the largest XOR is the one that differs from my number in the highest possible bit, then in the next highest, and so on. So you want to ask, bit by bit: "is there a number whose top bit is the opposite of mine? and among those, whose next bit is opposite?"

A trie answers exactly that. Write each number with the same number of bits, say 3, and store it as a path of 0s and 1s from the root, high bit first. Each node has at most two children.

1. Insert 5 = 101: root → 1 → 0 → 1.
2. Insert 2 = 010: root → 0 → 1 → 0. The root now has both a 0-child and a 1-child.
3. Insert 7 = 111: root → 1 (exists) → 1 (new) → 1 (new).
4. Insert 3 = 011: root → 0 (exists) → 1 (exists) → 1 (new).

Levels after all inserts: root → {0 → 1 → {0, 1}, 1 → {0 → 1, 1 → 1}}.

Now query with 5 = 101. At the root, my bit is 1, so I want a 0-child: it exists, take it, and the result's top bit is 1. Next my bit is 0, I want a 1-child under that node: exists, take it. Next my bit is 1, I want a 0-child: exists. The path walked is 010 = 2, and 5 ⊕ 2 = 111 = 7. Query each number the same way and keep the best; the maximum is 7.

Why it is correct

The invariant: after deciding the top k bits, the walk is inside the set of stored numbers that share those decisions, and the partial result is the largest achievable for the top k bits. The greedy step is safe because of place value: the bit at position k is worth 2^k, more than all lower bits together, since 2^k−1 + … + 1 = 2^k − 1. So if a 1 can be obtained at this bit by going to the opposite child, no choice at lower bits could ever make up for giving it away. When the opposite child does not exist, every remaining candidate agrees with me at this bit, and the bit is 0 for all of them, so following the same child loses nothing.

2^k > 2^k−1 + 2^k−2 + … + 1 = 2^k − 1

Why it is fast

Numbers have at most 32 bits, so each insert walks 32 nodes and each query walks 32 nodes. For n numbers that is 32n inserts plus 32n query steps: O(32 · n), which is linear. For 100,000 numbers that is about 6.4 million steps against 5 billion pairs. Memory is at most 32n nodes.

How to recognise it in an interview

Cues: maximum XOR, "XOR with an element from the array", pairs whose XOR is in a range, anything bitwise with "choose a partner from a set". Say: XOR is decided from the top bit down, so I will store the numbers in a binary trie and walk the opposite bit greedily. Maximum XOR of Two Numbers in an Array is the example. Maximum XOR With an Element From Array adds a limit: sort the queries and insert numbers only up to the limit before answering each.

02The idea in one line

Insert numbers bit by bit; for a query walk the opposite bit whenever possible.

Reach for it when: Maximum XOR of two numbers, maximum XOR with an element, count pairs with XOR in range.

Cost: O(n · 32) time.

03The walk-through, step by step

The video works one example: Max XOR of [3,10,5,25,2,8]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Insert every number bit by bit, high bit first
2. insert 5 = 101
3. insert 2 = 010
4. insert 7 = 111
5. insert 3 = 011
6. query 5 = 101: at each level take the opposite bit if it exists
7. walk gives partner 010 = 2: 5 ⊕ 2 = 7
8. query 2 = 010: at each level take the opposite bit if it exists
9. walk gives partner 101 = 5: 2 ⊕ 5 = 7
10. Repeat for every number; the maximum pair XOR is 7 (5 ⊕ 2)
11. n inserts and n queries of 32 steps each: O(32·n)

04Asked at Google

2 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Trie: Trie for prefix queries, Trie-guided grid DFS.