421. Maximum XOR of Two Numbers in an Array

421

MediumTrie and Advanced String SearchBinary trie of bits (or prefix hash set)Greedy bit-by-bit maximization

Maximum XOR of Two Numbers in an Array

Given an integer array nums, return the maximum value of nums[i] XOR nums[j] over all pairs of indices i and j.

In plain English

Find the pair of numbers whose bitwise XOR is as large as possible.

Picture it like this

Like choosing a dance partner whose outfit contrasts yours as much as possible, starting with the most visible feature (the top bit) and working down.

Example

Input: nums = [3, 10, 5, 25, 2, 8]
Output: 28
Why: 5 XOR 25 = 28, the largest XOR achievable by any pair.

Constraints

1 <= nums.length <= 2 * 10^50 <= nums[i] <= 2^31 - 1

Pattern lesson

See the pattern, then code

Greedy bit-by-bit maximization

↗

Trie and Advanced String Search

Repeated prefix lookup, autocomplete, dictionary search, or many-word matching.. XOR is maximized greedily from the top bit: at each bit you prefer a number whose bit is opposite the current one, since an opposite bit contributes a 1 to that (highest remaining) position.

New words, made simpleKnow these before the algorithm

XOR: Bit is 1 exactly when the two input bits differ.
Binary trie: A trie where each node has at most two children, keyed by bit 0 or 1.
Greedy on bits: Locking in the best possible value one bit at a time from most to least significant.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Brute force pairs

Too slow for n up to 2*10^5.

Compute XOR for every pair and keep the max.

Time O(n^2)Space O(1)

Best choiceBinary trie greedy

Linear-ish and finds the exact optimum by construction.

Store bit paths in a trie; for each number chase the opposite bit at every level.

Time O(32 n)Space O(32 n)

The rule we keep true

Invariant

After processing the top k bits for a query number, the running value equals the largest XOR prefix achievable against some stored number over those k bits.

Why this is correct

Reasoning

A higher bit outweighs all lower bits combined, so greedily securing a 1 at the highest possible position can never be beaten by any choice made at lower positions; the trie guarantees the opposite bit is chosen whenever some stored number offers it.

The algorithm in three movesSay these aloud before coding

1Insert each number into a binary trie, one node per bit from bit 31 down to 0

5 = ...00101

2For each number, walk the trie choosing the opposite bit branch when it exists

25 = ...11001

3Shift a 1 into the running answer whenever the opposite branch is taken

5^25 = 11100 = 28

4Track the maximum answer across all numbers

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

251

XOR2

283

1 · Readnums

2 · AskBit path of each?

3 · Update statetrie holds 6 bit paths

4 · ResultTrie built

Key takeaway

5 XOR 25 flips into 11100 (28), the maximum over all pairs.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-8Insert bit paths
Each number is stored as a 32-deep path keyed by its bits from MSB to LSB.
2
Lines 10-22Greedy query
For each number, prefer the opposite-bit child; taking it shifts a 1 into cur, otherwise a 0.
3
Lines 23Track best
The maximum over all query numbers is the answer.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Single element array yields 0 (i and j may be equal, x^x=0)
All identical numbers give 0
Includes 0 as an element
Values near 2^31 - 1

Common beginner mistakes

Iterating bits low-to-high instead of high-to-low breaks the greedy choice
Using too few bits so large values lose their top bit
Forgetting a number can pair with itself, though that only yields 0
Confusing the opposite bit (1 - bit) with the same bit

Check your understanding

Why go from the most significant bit downward rather than upward?

PyPython 3 · solution.py

Optimal

1class Solution:2    def findMaximumXOR(self, nums: List[int]) -> int:3        root = {}4        for num in nums:5            node = root6            for i in range(31, -1, -1):7                bit = (num >> i) & 18                node = node.setdefault(bit, {})9        best = 010        for num in nums:11            node = root12            cur = 013            for i in range(31, -1, -1):14                bit = (num >> i) & 115                toggle = 1 - bit16                if toggle in node:17                    cur = (cur << 1) | 118                    node = node[toggle]19                else:20                    cur = cur << 121                    node = node[bit]22            best = max(best, cur)23        return best

Time complexityO(n * 32)Optimized

Space complexityO(n * 32) for the trieExplained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

GoogleAmazonMeta

Maximum XOR of Two Numbers in an Array

Maximum XOR of Two Numbers in an Array

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Trie and Advanced String Search