Maximum XOR of Two Numbers in an Array
Last Updated: March 29, 2026
Understanding the Problem
We need to pick two numbers from the array (they can be the same element, since i can equal j) and XOR them together, then return the largest XOR result possible across all pairs.
XOR (exclusive or) compares corresponding bits of two numbers. If the bits differ, the result bit is 1. If they match, it's 0. So to maximize the XOR, we want two numbers whose binary representations differ in as many high-order bit positions as possible. A 1 in bit position 30 is worth more than having 1s in every position from 0 to 29 combined, so the strategy is greedy: try to make the highest bit a 1 first, then the next highest, and so on.
This "maximize bit by bit from the top" thinking is the key observation that drives both optimal approaches.
Key Constraints:
1 <= nums.length <= 2 * 10^4→ With n up to 20,000, an O(n^2) brute force would perform up to 400 million operations. That's borderline and might TLE depending on constant factors. We should aim for something better.0 <= nums[i] <= 2^31 - 1→ Values are non-negative 32-bit integers. This means at most 31 bits to consider. Any approach that iterates over bits adds a factor of at most 31, which is essentially constant.
Approach 1: Brute Force
Intuition
The simplest idea: try every pair. For each pair (i, j), compute nums[i] XOR nums[j] and track the maximum. No clever tricks, just exhaustive search.
XOR is cheap to compute (a single CPU instruction), so even though we're checking O(n^2) pairs, each check is fast. For small arrays this is perfectly fine.
Algorithm
- Initialize
maxXor = 0. - For each index
ifrom 0 to n-1, for each indexjfromito n-1, computenums[i] XOR nums[j]. - Update
maxXorif the current XOR is larger. - Return
maxXor.
Example Walkthrough
Code
- Time Complexity: O(n^2). We check every pair of elements. There are n*(n+1)/2 pairs, each requiring O(1) work for the XOR and comparison.
- Space Complexity: O(1). We only use a single variable to track the maximum.
The brute force checks all O(n^2) pairs without leveraging the bit structure of XOR. What if we could build the answer one bit at a time, checking at each level whether a given bit can be set to 1?
Approach 2: Bitwise Prefix with Hash Set
Intuition
Here's the key insight: we can build the maximum XOR one bit at a time, from the most significant bit (MSB) down to the least significant bit (LSB).
At each bit position, we ask: "Can we set this bit to 1 in our answer?" If yes, we keep it. If no, we leave it as 0 and move on to the next bit.
But how do we check whether a particular bit can be set? This is where a clever XOR property comes in: if a XOR b = c, then a XOR c = b. So if we want to know whether there exist two numbers in the array whose XOR has a certain prefix, we can store all the prefixes in a hash set, then for each prefix p, check whether p XOR candidateAnswer exists in the set. If it does, two numbers can produce that candidate answer.
The algorithm exploits a fundamental XOR identity: if a XOR b = c, then a XOR c = b. This means we can "reverse" the question. Instead of asking "what's the maximum XOR of any pair?", we ask "is this specific XOR value achievable?" and work our way down from the highest possible value.
By building the answer greedily from the most significant bit, we ensure we always get the largest possible result. Setting bit 30 to 1 (if possible) is worth more than any combination of lower bits. Once we've committed to the high bits, we try to set each subsequent bit, which can only increase the answer.
Algorithm
- Initialize
maxXor = 0. - For each bit position
kfrom 30 down to 0 (since max value is 2^31 - 1, bit 30 is the highest that can be set):
a. Compute candidate = maxXor | (1 << k) — this is the best answer so far with bit k tentatively set to 1.
b. Extract the prefix of each number by right-shifting by k bits: prefix = num >> k for every num. Store all prefixes in a hash set.
c. For each prefix p in the set, check if p XOR (candidate >> k) also exists in the set.
d. If yes, set maxXor = candidate (we confirmed bit k can be 1).
e. If no prefix pair produces the candidate, maxXor stays unchanged (bit k remains 0).
- Return
maxXor.
Example Walkthrough
Code
- Time Complexity: O(31 * n) = O(n). We iterate through 31 bit positions. At each position, we build a set of prefixes (O(n)) and check each prefix against the set (O(n) with O(1) average hash lookups).
- Space Complexity: O(n). The hash set stores at most n prefixes at each bit position.
The hash set approach is already O(n) but involves rebuilding the set 31 times with hash overhead. What if we stored all numbers in a binary trie and walked it greedily, choosing the opposite bit at every step?
Approach 3: Binary Trie (Optimal in Practice)
Intuition
Think of every number as a 31-bit binary string. If we insert all numbers into a trie where each node branches on 0 or 1, we get a binary trie that represents the entire array.
Now for each number, we want to find the number in the trie that maximizes the XOR with it. Since XOR produces a 1 when bits differ, at each level of the trie we greedily choose the opposite bit if possible. If the current number has a 0 at bit k, we try to go down the 1-branch of the trie (and vice versa). If the opposite branch doesn't exist, we're forced to take the same-bit branch (which contributes 0 to the XOR at that position).
This greedy walk through the trie for each number gives us the maximum XOR partner in O(31) time per number.
The trie stores every number's binary representation as a path from root to leaf. When we query for a number's best XOR partner, we walk the trie making the greedily optimal choice at every level: pick the opposite bit whenever possible, because differing bits produce 1s in the XOR result.
This greedy strategy is correct because higher bits are exponentially more valuable than lower bits. Setting bit k to 1 contributes 2^k to the XOR. Since 2^k > 2^(k-1) + 2^(k-2) + ... + 2^0, there's never a reason to sacrifice a high bit to gain all the lower bits. So the greedy approach from MSB to LSB always finds the global optimum.
Algorithm
- Build a binary trie: for each number in the array, insert its binary representation (31 bits, from MSB to LSB) into the trie.
- For each number in the array, traverse the trie greedily:
a. At each bit position (from bit 30 down to 0), check the current bit of the number.
b. Try to go to the child with the opposite bit (this maximizes XOR at this position).
c. If the opposite child doesn't exist, go to the same-bit child.
d. Accumulate the XOR result based on which path was taken.
- Track the maximum XOR across all numbers.
- Return the maximum.
Example Walkthrough
Code
- Time Complexity: O(31 n) = O(n). Inserting n numbers into the trie takes O(31 n). Querying n numbers takes O(31 * n). Total: O(62n) = O(n).
- Space Complexity: O(31 n) = O(n). The trie has at most 31 n nodes, each storing two child pointers. In practice, shared prefixes reduce this.