Maximum XOR of Two Numbers in an Array
Medium · Tries · Array · Hash Table · Bit Manipulation · Trie
Problem
You are given an integer array nums of non-negative numbers. Return the largest value of nums[i] XOR nums[j] over all 0 <= i <= j < n.
Choosing i == j gives 0, so the answer is never negative, and an array with one element answers 0.
Checking every pair works but costs O(n²). The intended solution stores the numbers bit by bit in a binary trie and, for each number, walks the trie toward the opposite bit wherever it can, building its best partner in about 31 steps.
Examples
Input: nums = [6,9,12,1] Output: 15
6 XOR 9 = 0110 XOR 1001 = 1111 = 15, and no pair can do better with four bits.
Input: nums = [7] Output: 0
The only choice is 7 with itself, which gives 0.
Input: nums = [2,4,8,16] Output: 24
The two highest bits come from 8 and 16: 8 XOR 16 = 24.
Constraints
- 1 <= nums.length <= 2 * 10^5
- 0 <= nums[i] <= 2^31 - 1
Approaches
- Baseline: every pair — time O(n²), space O(1)
Follow-up
The trie answers "which stored number XORs best with x" in O(bits) for any x, so it also serves queries that arrive one by one, and with prefix XORs it finds the subarray with the largest XOR. The use cases do both.
Related problems
Start free on Cariara · Coding problems · System design studio
