Maximum XOR of Two Numbers in an Array
Problem
nums, return the largest value of
nums[i] ^ nums[j] over all index pairs with 0 ≤ i ≤ j < n
(so pairing a number with itself, giving 0, is allowed).nums = [3,10,5,25,2,8]Output28 (5 ^ 25)nums = [14,70,53,83,49,91,36,80,92,51,66,70]Output127nums = [7]Output01 ≤ n ≤ 2·105 · 0 ≤ nums[i] ≤ 231 - 1
Try it yourself
class Solution {
public int findMaximumXOR(int[] nums) {
}
}
Instinct Many words, shared prefixes, and questions like "starts with", autocomplete, wildcard match or "search a board for all these words" - build a prefix tree.
Memory hack Words share their beginnings, so store each beginning once - walk one letter per step, and an end flag marks where a real word stops.
Open the Trie guide →Approaches
Brute ForceTry Every Pair
O(n2)Space O(1)XOR every pair (i, j) with i < j and keep the maximum.
The answer starts at 0, which covers a single element paired with itself.
public int findMaximumXOR(int[] nums) { int best = 0; for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { best = Math.max(best, nums[i] ^ nums[j]); } } return best; }
Trivially correct, but 2·1010 pairs at the upper limit.
BetterGreedy Bit-by-Bit with a Prefix Hash Set
O(31 · n)Space O(n)Build the answer one bit at a time from bit 30 down. With the top bits fixed in
best, try candidate = best | (1 << bit): it is reachable
iff two prefixes p, q (numbers masked to the top bits) satisfy
p ^ q == candidate, i.e. p ^ candidate is in the set.
public int findMaximumXOR(int[] nums) { int best = 0, mask = 0; for (int bit = 30; bit >= 0; bit--) { mask |= 1 << bit; Set<Integer> prefixes = new HashSet<>(); for (int x : nums) prefixes.add(x & mask); int candidate = best | (1 << bit); for (int p : prefixes) { if (prefixes.contains(p ^ candidate)) { // a ^ b = c <=> a ^ c = b best = candidate; break; } } } return best; }
Linear and elegant, but rebuilds a boxed HashSet 31 times (heavy constants).
OptimalBinary Trie, Greedy Opposite-Bit Walk
O(31 · n)Space O(31 · n)Store each number as a 31-level path of bits (high to low) in a binary trie.
To find the best partner for x, walk down preferring the child with the
opposite bit; each successful step sets that bit of the XOR. Insert-then-query
each number so every pair is considered exactly once.
private static class Node { Node[] child = new Node[2]; } public int findMaximumXOR(int[] nums) { Node root = new Node(); int best = 0; for (int x : nums) { // insert x Node cur = root; for (int bit = 30; bit >= 0; bit--) { int b = (x >> bit) & 1; if (cur.child[b] == null) cur.child[b] = new Node(); cur = cur.child[b]; } // best partner for x among numbers inserted so far (including x) cur = root; int xor = 0; for (int bit = 30; bit >= 0; bit--) { int b = (x >> bit) & 1; if (cur.child[1 - b] != null) { xor |= 1 << bit; cur = cur.child[1 - b]; } else { cur = cur.child[b]; } } best = Math.max(best, xor); } return best; }
Same linear bound as the set, but one pass with plain array lookups.
int[31*n+1][2]
array — same algorithm, far less GC pressure.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Try Every Pair | O(n2) | O(1) |
| Better | Greedy Bit-by-Bit with a Prefix Hash Set | O(31 · n) | O(n) |
| Optimal | Binary Trie, Greedy Opposite-Bit Walk | O(31 · n) | O(31 · n) |
- Starting at bit 31: inputs are non-negative, so bit 30 is the highest that can be set.
- Querying an empty trie — insert first (or seed with one number) so the walk never hits null.
- In the set method, forgetting to widen
maskeach round, so prefixes stay too short.
- Say why greedy works: bit k outweighs bits 0..k-1 combined (2k > 2k-1).
- Draw a 3-bit trie with a couple of numbers and walk the opposite-bit path aloud.
- Mention the hash-set version as a trie-free alternative with identical big-O.